[Boost] [GGL] Bost.Polygon (GTL) vs GGL - rationale

Hi, I am trying to understand the goemetry libraries. I find the currently under review GGL very useful for non-cartesian geometries (and maybe cartesian too!) but I don't understand what was the rationale for accepting GTL, which is a library mainly used in chip design. The reviews for GTL clearly stated that the library was not appropiate for GIS-like applications as its focus is mainly 2D. So, can anybody explain how these two libraries fit together. I see in which cases GGL will be useful but I am rather confused with Boost.Polygon, as it's optimized for VLSI design (as stated in the BoostCon paper and by some of the reviewers) Did someone decide that it was not possible to have a single GENERIC GEOMETRY library and we should have two ? thanks

Jose wrote:
Did someone decide that it was not possible to have a single GENERIC GEOMETRY library and we should have two ?
Somebody that studied informatics might like the term "GENERIC GEOMETRY", but somebody that actually took lessons in geometry might have a different opinion. A look at my book shelf reveals that I own at least the following books on geometry: Jean Fresnel; "Méthodes modernes en géométrie" Marcel Berger; "Géométrie 1" Marcel Berger; "Géométrie 2" Marcel Berger, Bernard Gostiaux; "Géométrie différentielle: variétés, courbes et surfaces" Marcel Berger; "A Panoramic View of Riemannian Geometry" Günter Aumann, Klaus Spitzmüller; "Computerorientierte Geometrie" Oswald Giering, Hans Seybold; "Konstruktive Ingenieursgeometrie" OK, most of all this shows that I like the books of Marcel Berger, but that is not the point I want to make. A bird eyes view on the "Table des matières" of Jean Fresnel's book can be summarized as follows A. Géométrie affine B. Géométrie projective C. Géométrie euclidienne D. Géométrie non euclidienne Is there something that these different geometries have in common? I guess a very good answer to this question is the "Erlangen program" by Felix Klein (http://en.wikipedia.org/wiki/Erlangen_program). The essence is that you could look at the hierarchy of their "group of symmetries" and study their invariants. However, there is also "convex geometry" (Chapitre 11. Ensemble convexes and Chapitre 12. Polytopes. Convexes compacts in Marcel Berger; "Géométrie 2") which is probably not well covered by the "Erlangen program", so I'm not completely sure about this. The point I want to make is that if somebody requested a single "GENERIC INFORMATIC" library, you would probably realize that this request is not reasonable. However, to request a single "GENERIC GEOMETRY" library is probably not significantly more reasonable. So what about CGAL? The "Computational Geometry Algorithms Library" (CGAL) is a collection of data structures and algorithms that cover much ground. However, would you call CGAL a "GENERIC GEOMETRY" library? Or even a "GENERIC COMPUTATIONAL GEOMETRY" library? Now Boost.Polygon has a set of algorithms that make sense in a VLSI context, and tried to build up a hierarchy of geometrical concepts well suited for the set of available algorithms. The implementations of these algorithms in Boost.Polygon often won't work well with floating point coordinates, because these algorithms were developed with fixed point coordinates in mind. (Because everybody pushes him, Luke tries to come up with some solution for the "floating point issue", but we should realize that this is a really difficult problem. So I can understand that Luke points out problems in the floating point code of GGL, because he doubts that they could solve the problems that are nearly unsolvable for him.) The concepts themselves have no problems with floating point coordinates, but does this really matter? Now GGL on the other hand excluded most of the implemented algorithms from the review by declaring them as extensions, and focused on providing a "dimension-agnostic, coordinate-system-agnostic and scalable kernel". Boost.Polygon obviously focused on fixed point coordinates in 2D, but is GGL really significantly less focused on 2D? I don't know. At least it is not focused on fixed point coordinates. Regards, Thomas

Hi, I am not expert in geometry but what matters is that boost continues to provide generic libraries (if possible !) like BGL, GIL, .. I think there is no blame on library authors which make a huge effort. What was broken is the review process, and some of the reasons why the review process was broken were: 1) The result of the review was 6 positive to 4 negative, when boost normally aims for consensus. This is the most objective point. Also, the issues the review manager was proposing to be fixed would not change the votes as the library was not appropiate even for 2D geo applications 2) The scope of GTL was changed before the review (see snippet 2 at the end) but the review docs still mention a wider app focus (see snippet 1 at the end). This confusion appeared when GTL was being reviewed. 3) The review manager didn't have time for the review (if you look at the apology at the beginning of the review email summary) 4) The GGL library proposal, which had been iterating the design with input from boost, in my opinion received an unfair treatment in the way the schedule was managed. 5) Boost failed to set the scope for a geometry library/ies and created tension with candidate library authors There are more points but I don't like long emails. I propose to change the current review process: http://www.boost.org/community/reviews.html ----------------- NOTES FOR REVIEW MANAGERS Decides if there is consensus to accept the library, and if there are any conditions attached. ----------------- AMENDMENT 1 that consensus should be objectively measured (with the votes) and otherwise the right to accept solely by the review manager could be revoked. Clearly there was no consensus in this library, and no clear discussion if one single library was possible (I understand your points that multiple libraries in this case may be preferable but still that is not incompatible with a complete design discussion) AMENDMENT 2 The review manager should have or have had no business ties with the library author/organization. Amendment 2 is not related to this review, but this would support the current transparency. I feel that in some cases there might be a vague prejudice in favor of big/important/known organizations to get their libraries accepted regards jose --------------------------------------------- Snippet from Boost.Polygon docs http://svn.boost.org/svn/boost/sandbox/gtl/doc/index.htm "These so-called Boolean algorithms are of significant interest in GIS (Geospatial Information Systems), VLSI CAD as well al other fields of CAD, and many more application areas, and providing them is the primary focus of this library." 7/19/09 I am changing the name of my library from GTL (Geometry Template Library) to boost::polygon and narrowing the scope from "computational geometry" to "polygon manipulation". This scope precisely describes the current scope of what is implemented. It also clarifies the position of the library relative to similar proposals. ------------------------------------------------

Jose wrote:
5) Boost failed to set the scope for a geometry library/ies and created tension with candidate library authors
I agree with this. I think that in the rush to get their own vision of a geometry kernel accepted, all the geometry authors let go the notion of having a single common representation for each geometry type. Unfortunately as can be seen from the discussions about geometry there hasn't been consensus on much of anything. Well, beyond the more trivial things like agnostic compile time access to coordinate sequences (the bicycle shed.)
Clearly there was no consensus in this library, and no clear discussion if one single library was possible (I understand your points that multiple libraries in this case may be preferable but still that is not incompatible with a complete design discussion)
I did vote that Polygon should be accepted and still believe it should based on its merits. I should note that subsequent disagreements have already come about WRT how data structures are different between GGL and Polygon (specifically the way polygons are defined). Clearly the community has so far failed to produce a way of defining geometry in a form that arguably should be common for all geometry libraries. I suspect this happens because most of the authors have the goal of adapting long term projects into a Boost library rather than building a common one from scratch. I suppose the question is whether the community should be reinforcing this practice? Regards, Brandon

On Mon, Nov 16, 2009 at 2:41 PM, Brandon Kohn <blkohn@hotmail.com> wrote:
Jose wrote: > 5) Boost failed to set the scope for a geometry library/ies and
created tension with candidate library authors
I agree with this. I think that in the rush to get their own vision of a geometry kernel accepted, all the geometry authors let go the notion of having a single common representation for each geometry type. Unfortunately as can be seen from the discussions about geometry there hasn't been consensus on much of anything. Well, beyond the more trivial things like agnostic compile time access to coordinate sequences (the bicycle shed.)
It seems logical the authors will always try to push their library but it should be a separate discussion (maybe before the review process) that clarifies what boost wants and doesn't want. I think this discussion is necessary now because the early boost libraries had a narrower scope but the newer ones are much broader in scope.
Clearly there was no consensus in this library, and no clear discussion if one single library was possible (I understand your points that multiple libraries in this case may be preferable but still that is not incompatible with a complete design discussion)
I did vote that Polygon should be accepted and still believe it should based on its merits. I should note that subsequent disagreements have already come about WRT how data structures are different between GGL and Polygon (specifically the way polygons are defined). Clearly the community has so far failed to produce a way of defining geometry in a form that arguably should be common for all geometry libraries. I suspect this happens because most of the authors have the goal of adapting long term projects into a Boost library rather than building a common one from scratch. I suppose the question is whether the community should be reinforcing this practice?
Yes, your description explains it nicely ! Now is the time to update the way the process works so that we don't get into this mess again. The logical steps I see are: 1) Is it possible to have an encompassing library ("generic") that can accept multiple geometries and algorithms ? 2) If no, then have separate libaries Else, then take the most generic base and try to make sure multiple application domains are happy. This is the theory, but in practice, when the library being proposed by corp authors (instead of typical boost case of individual authors) then there is little incentive to cooperate but the community should have clear guidelines about this. If it were my decision, I would withdraw the just accepted library because of the faulty review and to set a precedent. But it's really hard to walk backwards to walk forward later on!
Regards,
Brandon
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Jose wrote:
Hi,
I am not expert in geometry but what matters is that boost continues to provide generic libraries (if possible !) like BGL, GIL, ..
I think there is no blame on library authors which make a huge effort. What was broken is the review process, and some of the reasons why the review process was broken were:
1) The result of the review was 6 positive to 4 negative, when boost normally aims for consensus. This is the most objective point. Also, the issues the review manager was proposing to be fixed would not change the votes as the library was not appropiate even for 2D geo applications
There were two primary issues the no votes pointed out. One was performance, which it turns out was a red herring exactly as the review manager concluded. The other was support for floating point. The interfaces support floating point while the polygon clipping algorithm does not. It is unreasonable to ask me to implement a 2nd algorithm equal in scale to the first, since that is what would be required to add floating point support. Once I am able to call a good implementation of polygon intersection that is licensed under the boost license the 2nd objection will also be addressed. I am hoping that GGL might one day contain that implementation, but right now it does not.
2) The scope of GTL was changed before the review (see snippet 2 at the end) but the review docs still mention a wider app focus (see snippet 1 at the end). This confusion appeared when GTL was being reviewed.
There is no inconsistency there. Polygons are used in GIS and fixed point booleans are used in GIS.
3) The review manager didn't have time for the review (if you look at the apology at the beginning of the review email summary)
The apology was for the delay releasing the result of the review. During the review the review manager was engaged and had already decided the result of the review shortly after the review concluded. The review manager was very responsive to my emails during and shortly after the review.
4) The GGL library proposal, which had been iterating the design with input from boost, in my opinion received an unfair treatment in the way the schedule was managed.
My library has actually been iterating the design with input from boost for longer than GGL. I did it in a more low key way than Barend, but I did iterate three or four times with the boost community on design and implementation issues over a period of years. What I think is unfair to GGL is that it was brought to review too soon. There are a number of issues and features not yet implemented that I think would have been better addressed before a formal review rather than after. Personally I think this should have been another preview rather than a review of GGL, that way we could provide feedback to Barend without people jumping to his defense and saying things are unfair. Regards, Luke

On Mon, Nov 16, 2009 at 9:19 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
There were two primary issues the no votes pointed out. One was performance, which it turns out was a red herring exactly as the review manager concluded. The other was support for floating point. The interfaces support floating point while the polygon clipping algorithm does not. It is unreasonable to ask me to implement a 2nd algorithm equal in scale to the first, since that is what would be required to add floating point support. Once I am able to call a good implementation of polygon intersection that is licensed under the boost license the 2nd objection will also be addressed. I am hoping that GGL might one day contain that implementation, but right now it does not.
Hi Luc, My point is at a higher level. When there are important library contributions that overlap, like Barend and yours, then Boost has to find a way to integrate both of them. As each library is from a different application domain, each has its own strengths and weaknesses. The issue here is about cooperation rather than confrontation !
2) The scope of GTL was changed before the review (see snippet 2 at the end) but the review docs still mention a wider app focus (see snippet 1 at the end). This confusion appeared when GTL was being reviewed.
There is no inconsistency there. Polygons are used in GIS and fixed point booleans are used in GIS.
The issue is that Boost aims for generic libraries if possible, so the fact that the scope changed means that the fit is different. I think the good intentions of the reviewer were that the library has good algorithms/implementations so lets have them in Boost. But, from a broader viewpoint I think more coordination is necessary.
4) The GGL library proposal, which had been iterating the design with input from boost, in my opinion received an unfair treatment in the way the schedule was managed.
My library has actually been iterating the design with input from boost for longer than GGL. I did it in a more low key way than Barend, but I did iterate three or four times with the boost community on design and implementation issues over a period of years. What I think is unfair to GGL is that it was brought to review too soon. There are a number of issues and features not yet implemented that I think would have been better addressed before a formal review rather than after. Personally I think this should have been another preview rather than a review of GGL, that way we could provide feedback to Barend without people jumping to his defense and saying things are unfair.
I know you have received a lot of input from the reviewer (as acknowledged in your boostcon paper) and the reviewer is interested in your algorithms, as expressed in emails. My interest is in a library that fits the different application domains well and it's great that there are authors with experience in these different domains regards jose

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jose Sent: Sunday, November 15, 2009 9:54 AM To: boost@lists.boost.org Subject: [boost] [Boost] [GGL] Bost.Polygon (GTL) vs GGL - rationale
I am trying to understand the goemetry libraries.
I find the currently under review GGL very useful for non-cartesian geometries (and maybe cartesian too!) but I don't understand what was the rationale for accepting GTL, which is a library mainly used in chip design. The reviews for GTL clearly stated that the library was not appropiate for GIS-like applications as its focus is mainly 2D.
So, can anybody explain how these two libraries fit together. I see in which cases GGL will be useful but I am rather confused with Boost.Polygon, as it's optimized for VLSI design (as stated in the BoostCon paper and by some of the reviewers)
Did someone decide that it was not possible to have a single GENERIC GEOMETRY library and we should have two ?
I think this about to be decided (implicitly - if GGL is accepted too, as reviews so far might suggest). FWIW, I concluded from the long discussions that although it would be neat to have one generic library, it wasn't quite time for that because there were too many unanswered difficulties (mainly about robustness and floating-point) in using GGL to implement GTL. And using a generic system might always require too big a compromise on performance, as the regrettably acrimonious dispute over benchmarks shows. (I wonder if the acrimony has been inflamed by the fear that only one could get the 'prize' of being accepted into Boost.) The problem domains appear to me to have quite different needs for speed, accuracy and robustness. FWIW, I see no reason why the two should not coexist in Boost, until such time as it is found possible to implement GTL efficiently enough using a generic library. Let users vote with their mice ;-) Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
participants (5)
-
Brandon Kohn
-
Jose
-
Paul A. Bristow
-
Simonson, Lucanus J
-
Thomas Klimpel