GTL - geometric template library - determining interest
Count me as very interested. This is a needed library and I would be interested in making shur that it is compatible and usable with boost::gil. (the graphics library)
Tom Brinkman wrote:
Count me as very interested. This is a needed library and I would be interested in making shur that it is compatible and usable with boost::gil. (the graphics library)
That would be awesome. Gyuszi
Count me as interested in any attempt at a free generic geometry library. Is this purely 'rectilinear' -- I mean, when you say polygons do you mean any kind of polygon or only the kinds of polygons formed by the union of axis-aligned rectangles? Could I find the intersection of a star and a triangle? Others have put forth some geometry library ideas here and I have not seen one take-off; for instance to my knowledge boosters have not even agreed on spatial point or vector classes or concepts. I personally simply want boost to accept a library with these fundamentals, so people can submit algorithms to the library over time and code I develop using these concepts will be compatible. I also suspect that CGAL (which apparently is not as free as boost) is making people feel like they have to do way too much in a geometry library. -- John
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Suto, Gyuszi Sent: Tuesday, October 02, 2007 9:58 AM To: boost@lists.boost.org Subject: Re: [boost] [GTL] - geometric template library - determininginterest
Tom Brinkman wrote:
Count me as very interested. This is a needed library and I would be interested in making shur that it is compatible and usable with boost::gil. (the graphics library)
That would be awesome. Gyuszi _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
John Femiani wrote:
Count me as interested in any attempt at a free generic geometry library.
Is this purely 'rectilinear' -- I mean, when you say polygons do you mean any kind of polygon or only the kinds of polygons formed by the union of axis-aligned rectangles? Could I find the intersection of a star and a triangle?
The polygons need to be formed by union of axis-aligned rectangles, yes. In addition to that, GTL supports 45 degree polygons as well. Can GTL intersect a star and a triangle? If both are limited to rectilinear or 45 degreee edges, yes, otherwise no. Gyuszi
Suto, Gyuszi wrote:
The polygons need to be formed by union of axis-aligned rectangles, yes. In addition to that, GTL supports 45 degree polygons as well. Can GTL intersect a star and a triangle? If both are limited to rectilinear or 45 degreee edges, yes, otherwise no.
Would it be possible to add classes for general polygons? Or is this an inherent constraint of your algorithms? Although I'm still curious, arbitrary edge orientations would be required for our application. Malte
Malte Clasen wrote:
Suto, Gyuszi wrote:
The polygons need to be formed by union of axis-aligned rectangles, yes. In addition to that, GTL supports 45 degree polygons as well. Can GTL intersect a star and a triangle? If both are limited to rectilinear or 45 degreee edges, yes, otherwise no.
Would it be possible to add classes for general polygons? Or is this an inherent constraint of your algorithms? Although I'm still curious, arbitrary edge orientations would be required for our application.
We don't have immediate plans to implement general polygons, but that's certainly a possibility. The biggest issue is agreeing on fixed vs. floating precision, what to do with slicing, whether to introduce triangle and/or trapezes as primitives, etc. The current data abstraction, isotropy, scan-lines would all hold. Gyuszi
Suto, Gyuszi wrote:
The biggest issue is agreeing on fixed vs. floating precision.
If it's going to be a template library why not both? I personally need fixed-point but I can easily see situations where using floating-point would be beneficial. Thanks, Michael Marcin
Michael Marcin wrote:
Suto, Gyuszi wrote:
The biggest issue is agreeing on fixed vs. floating precision.
If it's going to be a template library why not both?
I personally need fixed-point but I can easily see situations where using floating-point would be beneficial.
The floating point has high resolution near zero and very low resolution at high values. My worry is that once you start moving, creating, intersecting shapes/lines at high values, you may not have a floating point value available for that coordinate. Then you snap to nearest, in which case your parallels are not parallel any more, your collinears are not collinear any more, etc. There are many problems with floating points. Maybe infinite precision, maybe rational numbers will work. I'm sure some of the readers of this thread have more experience with that regards Gyuszi
Suto, Gyuszi wrote:
Michael Marcin wrote:
Suto, Gyuszi wrote:
The biggest issue is agreeing on fixed vs. floating precision.
If it's going to be a template library why not both?
I personally need fixed-point but I can easily see situations where using floating-point would be beneficial.
The floating point has high resolution near zero and very low resolution
at high values. My worry is that once you start moving, creating, intersecting shapes/lines at high values, you may not have a floating point value available for that coordinate. Then you snap to nearest, in which case your parallels are not parallel any more, your collinears are not collinear any more, etc. There are many problems with floating points. Maybe infinite precision, maybe rational numbers will work. I'm sure some of the readers of this thread have more experience with that regards Gyuszi
Ok, but then again, there are also problems with fixed point. So, again, why does the library have to choose and not the user, since we have templates? Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Suto, Gyuszi wrote:
The biggest issue is agreeing on fixed vs. floating precision.
If it's going to be a template library why not both?
The floating point has high resolution near zero and very low resolution at high values.
Joel de Guzman wrote:
Ok, but then again, there are also problems with fixed point. So, again, why does the library have to choose and not the user, since we have templates?
You are asking me what my rationale was for not templating the coordinate data type. That is a good and useful question to ask. It was a conscious decision I made based upon the benefit it would provide vs. the cost of adding an additional template parameter to each and every geometric class. Just because "we have templates" doesn't mean that we don't incur a cost in using them. The cost I was concerned with was ease of use, primarily. Similarly I didn't template the dimensionality of geometry types because the benefit (primarily saves me typing) wasn't justified by the added complexity and difficulty using the library that choice would have caused. Instead I chose to pay the costs of templating to get much bigger benefits from ease of integration. Incidentally, I do have a typedef for the coordinate data type, and you can easily change it to double, but the code wouldn't work. The built in equivalence operator is effectively meaningless in floating point and a lot of the code would become nonsensical. There is a big difference between fixed point geometry and its application domains and floating point geometry and its application domains. I am skeptical that a generic geometry library could successfully bridge that gap by templating the coordinate data type. Someone working in a floating point application domain should feel welcome to contribute the floating point library. Lucanus Simonson
Simonson, Lucanus J wrote:
Suto, Gyuszi wrote:
The biggest issue is agreeing on fixed vs. floating precision.
If it's going to be a template library why not both? The floating point has high resolution near zero and very low resolution at high values. Joel de Guzman wrote: Ok, but then again, there are also problems with fixed point. So, again, why does the library have to choose and not the user, since we have templates?
You are asking me what my rationale was for not templating the coordinate data type. That is a good and useful question to ask. It was a conscious decision I made based upon the benefit it would provide vs. the cost of adding an additional template parameter to each and every geometric class. Just because "we have templates" doesn't mean that we don't incur a cost in using them. The cost I was concerned with was ease of use, primarily.
What cost? Typing? You can default to fixed point. There's no cost AFAICT. Use typedefs for typical template instantiations. This is how GIL did it, or even std::basic_string and std::string.
Similarly I didn't template the dimensionality of geometry types because the benefit (primarily saves me typing) wasn't justified by the added complexity and difficulty using the library that choice would have caused. Instead I chose to pay the costs of templating to get much bigger benefits from ease of integration. Incidentally, I do have a typedef for the coordinate data type, and you can easily change it to double, but the code wouldn't work. The built in equivalence operator is effectively meaningless in floating point and a lot of the code would become nonsensical.
Generic programming techniques take care of that dilemma. There is
a big difference between fixed point geometry and its application domains and floating point geometry and its application domains. I am skeptical that a generic geometry library could successfully bridge that gap by templating the coordinate data type. Someone working in a floating point application domain should feel welcome to contribute the floating point library.
I disagree. Generic programming techniques can be used to sort out the data-type idiosyncrasies. See GIL for instance: a library that is so flexible as to what component types should be without sacrificing speed and ease of use. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Joel de Guzman wrote:
I disagree. Generic programming techniques can be used to sort out the data-type idiosyncrasies. See GIL for instance: a library that is so flexible as to what component types should be without sacrificing speed and ease of use.
Joel, this is exactly why we want to contribute GTL to boost to harness the knowledge of folks like you. Yes, there may be generic programming techniques that take care of the idiosyncracies and we welcome ideas, code examples. GTL is relatively generic i.e. it abstracts the user data away, and - as my colleague Lucanus mentioned - it has a typedef for the number type. I'm sure there are many ways to make it even more generic. My current focus is to work through the Intel legal channels to be able to put the code out there. From the e-mail traffic so far I'm sensing that there's genuine interest in it, and I'm happy about that. regards Gyuszi
Simonson, Lucanus J wrote:
It was a conscious decision I made based upon the benefit it would provide vs. the cost of adding an additional template parameter to each and every geometric class.
That you would need an *additional* template parameter would be a consequence of a particular use of temples. You could follow the CGAL way: all geometric classes are parametrized in a *single* traits class. The traits class itself provides all the types and operations needed.
Just because "we have templates" doesn't mean that we don't incur a cost in using them. The cost I was concerned with was ease of use, primarily. Similarly I didn't template the dimensionality of geometry types because the benefit (primarily saves me typing) wasn't justified by the added complexity and difficulty using the library that choice would have caused.
But parametrizing the coordinate type and the dimension are two different things. There is a finite mumber of practical dimensions, typically, (1..4) (Truly "D" dimensional geometry is a whole different game). But the choice of coordinate type is not merely fixed-point vs foating-point. There are interval number for filering, big-float numbers for sqrt-free none-rational arithmetic, lazy numbers for constructive reals, big integer rationals for exactly artihmetic, etc, etc, etc..
Instead I chose to pay the costs of templating to get much bigger benefits from ease of integration. Incidentally, I do have a typedef for the coordinate data type, and you can easily change it to double, but the code wouldn't work.
But it would work if you changed it with CORE::Expr for instance, just to name an example.
The built in equivalence operator is effectively meaningless in floating point and a lot of the code would become nonsensical.
Or, the operator would throw in the presence of uncertainty in the floating point comparison if an interval type is used. So a lot of code would work as fast as it can get so long it remains sensical, and give up as soon as it does not. And you could try the code again with a slower but exact number type. But none of this is possible if the arithmetic layer is not parametrized. As I said in a different post, discussions about basic geometric elements such as points need a different perspective than discussions about domain-specific elements like axis-aligned rectangles where fixed-point is such a good choice that parametrization is mostly pointless. -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
Suto, Gyuszi wrote:
We don't have immediate plans to implement general polygons, but that's certainly a possibility. The biggest issue is agreeing on fixed vs. floating
Why do you have to choose when there are templates? Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Suto, Gyuszi wrote:
In addition to that, GTL supports 45 degree polygons as well.
What exactly is a 45 degree polygon? (45 degree is *one* direction, but a poygon has many sides) Or do you mean that you can create a polygon as the overlay of rectangles alinged on a 45 degree axis? I that case, what about the other two sides of the rectangle? (that is, do you support parallelograms or just rectangles)? And in that case too, can you overlay a 45ยบ rect with a Horzontal rect? (I guess yes) -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
In addition to that, GTL supports 45 degree polygons as well.
Fernando Cacciola wrote:
What exactly is a 45 degree polygon? (45 degree is *one* direction, but a poygon has many sides)
Or do you mean that you can create a polygon as the overlay of rectangles alinged on a 45 degree axis?
I that case, what about the other two sides of the rectangle? (that is, do you support parallelograms or just rectangles)?
And in that case too, can you overlay a 45ยบ rect with a Horzontal rect? (I guess yes)
Your confusion is quite natural since we haven't submitted the code yet. At this stage, we should focus on clarifying what we are proposing submitting as opposed to details that could be answered by simply reading the code. In this case the answer is of central importance in understanding the nature of the submission. The algorithm is vertex based (not rectangle based as you had surmised.) It is an optimal implementation of the classical scanline algorithm for line segment intersection applied to Boolean operations over polygons (sequences of verticies) and handles all the "degenerate" cases that text books wave their hands at. It does not support arbitrary angles, and is limited to vertical, horizontal and 45 degree diagonal edges. In this way it can apply exact integer arithmetic and achieve maximal performance for that special case of data. Intel happens to handle terabytes of such data on a daily basis, so we have an obvious need for such. My team also has an older arbitrary angle Booleans implementation (not mine and not up to boost standards) so I'm not bluffing when I say we could contribute such in the near future. The question we all need to answer is if it is appropriate for boost. If it were nothing more than an industrial strength computational geometry algorithm the answer would probably be no. The important thing about the library is not so much *what* it does but *how*. As a library writer in an industrial setting I am faced with a challenge of how to overcome the complexity created by an explosion of C++ geometry types in numerous legacy applications. Integrating a superior library capability into pre-existing applications is a challenge due to type incapability. The important thing about my library is that I have solved that problem by applying C++ Concepts, inheriting my types from the template parameter, to allow a minimal concept map to provide the interface between my algorithms and the legacy system's geometry data types. We got so caught up in explaining to boost what we did that we forgot to mention why. These algorithms are of sufficient interest to Intel that we had half a dozen different (all suboptimal) implementations of them extant in multiple different legacy applications in my department alone. They are of interest to many of other companies, as well, each with their own implementations. My goal was not only to implement a superior library but also to minimize the effort required to integrate that library into the many legacy applications while not compromising on performance. The way I did that by applying C++ Concepts to overcome the problem of type incompatibility is of general interest to C++ library development. It ought to be easy for anyone to replace their legacy algorithms with mine if it were a boost library. As I see it, the value of boost is much bigger than the usefulness of the libraries. Boost is a way to teach a new generation of C++ developers how to make better use of the language by the example of the code that is shared. The usefulness of the libraries is just the bait to get people to read the code and learn from it. I think my library is useful enough that people will read the code and I think they will learn from it. That is why I am submitting my library to boost. P.S. my point2d data structure is a class encapsulated array of size 2. You can override it with your own, of course, through the template inheritance generic interface. Lucanus Simonson
Simonson, Lucanus J wrote:
The important thing about the library is not so much *what* it does but *how*. As a library writer in an industrial setting I am faced with a challenge of how to overcome the complexity created by an explosion of C++ geometry types in numerous legacy applications. Integrating a superior library capability into pre-existing applications is a challenge due to type incapability. The important thing about my library is that I have solved that problem by applying C++ Concepts, inheriting my types from the template parameter, to allow a minimal concept map to provide the interface between my algorithms and the legacy system's geometry data types.
Yes, we should focus on this. What do people think about the balance between (a) supporting legacy code that uses its own types and (b) simplifying the case where you're developing new code? Are there other examples in the standard library or Boost where this has been an issue? Is this a false dichotomy? My fear is that this "compatibility layer" could obfuscate the interface for new users with no legacy issues. I'm unclear about how symmetric the GTL or Fusion methods for adaptation are from the point of view of the library user vs. the library author. As I understand it, in both cases a library user can invent their own types and adapt them to work with the library. But a library author must always use the fusion get<n>(X) or equivalent GTL syntax. Is this true, or is there some way of using my choice of .xyz or [n] in the library code that I write? Regards, Phil.
Simonson, Lucanus J wrote:
As a library writer in an industrial setting I am faced with a challenge of how to overcome the complexity created by an explosion of C++ geometry types in numerous legacy applications. Integrating a superior library capability into pre-existing applications is a challenge due to type incapability. The important thing about my library is that I have solved that problem by applying C++ Concepts, inheriting my types from the template parameter, to allow a minimal concept map to provide the interface between my algorithms and the legacy system's geometry data types.
That's very good. I'm not quite sure about inheritance though.
P.S. my point2d data structure is a class encapsulated array of size 2. You can override it with your own, of course, through the template inheritance generic interface.
With the restriction that it has to be indexable by a runtime int? That is a severely limited concept of a point, I would say. And, again, I find the need for inheritance dubious. Inheritance gives you tight coupling. Something that you'd want to avoid when adopting a 3rd party type. It is possible to adopt a 2d-point from library A and library B without ever touching them. That's the very essence of generic programming. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Joel wrote:
That's very good. I'm not quite sure about inheritance though.
You can override it with your own, of course, through the template inheritance generic interface.
P.S. my point2d data structure is a class encapsulated array of size
With the restriction that it has to be indexable by a runtime int? That is a severely limited concept of a point, I would say. And, again, I find the need for inheritance dubious. Inheritance gives you tight coupling. Something that you'd want to avoid when adopting a 3rd party type. It is possible to adopt a 2d-point from library A and library B without ever touching them. That's the very essence of generic programming.
I put a lot of thought into the implications of inheritance, believe me. There is no restrition that it has to be indexable by a runtime int. Your point2d data type can and should be something like: struct MyLegacyPoint2D { int x; int y; }; Your concept map to my point2d concept class would look like: template <> class PointConceptMap<MyLegacyPoint2D> { static inline int PointGet(const MyLegacyPoint2D& t, Orientation2D orient) { return predicated_value(orient == HORIZONTAL, t.x, t.y); } static inline void PointSet(MyLegacyPoint2D& t, Orientation2D orient, int value) { predicated_assign(orient == HORIZONTAL, t.x, t.y, value); } static inline MyLegacyPoint2D PointConstruct(int xval, int yval) { MyLegacyPoint2D tmp; tmp.x = xval; tmp.y = yval; return tmp; } privte: PointConceptMap(); }; Your usage of your data type with my point concept would look like MyLegacyPoint2D pt; point_concept<MyLegacyPoint2D>& ptconcept = point_concept::mimic(pt); point_concept<point2d_data> gtlptconcept(10, 20); ptconcept.set(HORIZONTAL, 10); ptconcept.set(VERTICAL, 20); assert(ptconcept == gtlptconcept); You use my concept class's == operator with your data type to compare it to my data type. I have dozens of point2d concept class member functions that become available for you to use with your data type to interact with my data type. All this seems like overkill with simple point2d data types but when you have polygons that are sequences of vertices it becomes a Rosetta stone of type inter-compatibility and a mechanism for getting legacy data in and out of algorithms in a generic, zero cost of abstraction way that is minimal effort and very productive (not error prone.) When you realize that my Polygon concept class uses my Point concept class to interact with its vertices the whole picture suddenly becomes clear. Sometimes it is useful to have a polygon that is a linked list of points. Sometimes it is useful to have a vector, sometime it is useful to have a compressed storage for polygon data. The polygon concept class is the glue that can really tie everything together and make it all work together as smooth as butter. By the way if you have a 3D point you can view it as a 2D point (because conceptually it is a 2D point with extra semantics.) I do that all the time, and use it to refactor my higher dimension code instead of templating the dimensionality. It might have been better if I called it the Geometry Concepts Library, since the term template is too *ahem* generic. Lucanus Simonson
Simonson, Lucanus J wrote:
Joel wrote:
That's very good. I'm not quite sure about inheritance though.
You can override it with your own, of course, through the template inheritance generic interface.
P.S. my point2d data structure is a class encapsulated array of size
With the restriction that it has to be indexable by a runtime int? That is a severely limited concept of a point, I would say. And, again, I find the need for inheritance dubious. Inheritance gives you tight coupling. Something that you'd want to avoid when adopting a 3rd party type. It is possible to adopt a 2d-point from library A and library B without ever touching them. That's the very essence of generic programming.
I put a lot of thought into the implications of inheritance, believe me. There is no restrition that it has to be indexable by a runtime int.
Hmm. I was confused by your earlier post, it seems:
Moreover, the technique you are proposing works fine at compile time, but won't work if the axis of the coordinate you are accessing is a runtime parameter: int my_axis = 0; get<my_axis>(pt); will throw an error. We specify the axis we access at run time. If we specify a constant it should compile away and be light weight. gcc 4.2.1 still needs us to play with the compiler flags to get decent inlining. pt.get(orient.getPerpendicular()); //orientation determined at run time. My scanline algorithm actually parameterizes the orientation of the scanline at runtime, so you can sweep left to right or bottom to top.
[snip]
All this seems like overkill with simple point2d data types but when you have polygons that are sequences of vertices it becomes a Rosetta stone of type inter-compatibility and a mechanism for getting legacy data in and out of algorithms in a generic, zero cost of abstraction way that is minimal effort and very productive (not error prone.) When you realize that my Polygon concept class uses my Point concept class to interact with its vertices the whole picture suddenly becomes clear. Sometimes it is useful to have a polygon that is a linked list of points. Sometimes it is useful to have a vector, sometime it is useful to have a compressed storage for polygon data. The polygon concept class is the glue that can really tie everything together and make it all work together as smooth as butter.
By the way if you have a 3D point you can view it as a 2D point (because conceptually it is a 2D point with extra semantics.) I do that all the time, and use it to refactor my higher dimension code instead of templating the dimensionality.
It might have been better if I called it the Geometry Concepts Library, since the term template is too *ahem* generic.
I'll refrain on commenting on actual concept classes before I see any real code. Seems like an interesting concept; pun intentional, but I won't really know unless I see it and get to know the pros and cons of such an approach. I still doubt the inheritance approach, fwiw. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Simonson, Lucanus J wrote:
In addition to that, GTL supports 45 degree polygons as well.
Fernando Cacciola wrote:
What exactly is a 45 degree polygon? (45 degree is *one* direction, but a poygon has many sides)
Or do you mean that you can create a polygon as the overlay of rectangles alinged on a 45 degree axis?
I that case, what about the other two sides of the rectangle? (that is, do you support parallelograms or just rectangles)?
And in that case too, can you overlay a 45ยบ rect with a Horzontal rect? (I guess yes)
Your confusion is quite natural since we haven't submitted the code yet. At this stage, we should focus on clarifying what we are proposing submitting as opposed to details that could be answered by simply reading the code. In this case the answer is of central importance in understanding the nature of the submission. The algorithm is vertex based (not rectangle based as you had surmised.)
Ha, that's better.. much better. I was confused by this sentence from Gyuszi: "The polygons need to be formed by union of axis-aligned rectangles, yes."
It is an optimal implementation of the classical scanline algorithm for line segment intersection applied to Boolean operations over polygons (sequences of verticies) and handles all the "degenerate" cases that text books wave their hands at. It does not support arbitrary angles, and is limited to vertical, horizontal and 45 degree diagonal edges.
Ha OK, I see.
In this way it can apply exact integer arithmetic and achieve maximal performance for that special case of data.
Right.
Intel happens to handle terabytes of such data on a daily basis, so we have an obvious need for such. My team also has an older arbitrary angle Booleans implementation (not mine and not up to boost standards) so I'm not bluffing when I say we could contribute such in the near future.
Specially if the library is properly layered. The sweepline process (used by your algo) has many edge-angle-independent parts that can be factored out.
The question we all need to answer is if it is appropriate for boost.
I would say that at least the bottom layer is.
If it were nothing more than an industrial strength computational geometry algorithm the answer would probably be no. The important thing about the library is not so much *what* it does but *how*.
OK. This would be a good reason.
As a library writer in an industrial setting I am faced with a challenge of how to overcome the complexity created by an explosion of C++ geometry types in numerous legacy applications. Integrating a superior library capability into pre-existing applications is a challenge due to type incapability. The important thing about my library is that I have solved that problem by applying C++ Concepts, inheriting my types from the template parameter, to allow a minimal concept map to provide the interface between my algorithms and the legacy system's geometry data types.
OK. There are different ways in which you can approach a concept-based design, but is clear that a good modern library must follow one. Do expect some crictizism regarding the specific approach to concepts you have taken, but FWIW I like it better than the CGAL approach (which is also concept based).
We got so caught up in explaining to boost what we did that we forgot to mention why.
It happens :)
These algorithms are of sufficient interest to Intel that we had half a dozen different (all suboptimal) implementations of them extant in multiple different legacy applications in my department alone. They are of interest to many of other companies, as well, each with their own implementations. My goal was not only to implement a superior library but also to minimize the effort required to integrate that library into the many legacy applications while not compromising on performance. The way I did that by applying C++ Concepts to overcome the problem of type incompatibility is of general interest to C++ library development. It ought to be easy for anyone to replace their legacy algorithms with mine if it were a boost library.
OK. So one stated goal of your library is that it should be truly *generic*, meaning that a user should be abe to take some concrete facility and apply it to its own data structures.
As I see it, the value of boost is much bigger than the usefulness of the libraries. Boost is a way to teach a new generation of C++ developers how to make better use of the language by the example of the code that is shared.
Indeed.
The usefulness of the libraries is just the bait to get people to read the code and learn from it.
Being useful is one of the stated requirements for any boost library, but you have a point. If the library is really cool in the way it is designed and implemented, then one could argue that its usefullness lies exactly there. Best Fernando Cacciola
Fernando wrote:
There are different ways in which you can approach a concept-based design, but is clear that a good modern library must follow one. Do expect some crictizism regarding the specific approach to concepts you have taken, but FWIW I like it better than the CGAL approach (which is also concept based).
I welcome the criticism. I would like to learn some new things and improve on what I have done so far with the library. In particular I can probably do a few things to improve the error msgs people get when they hook things up incorrectly.
So one stated goal of your library is that it should be truly *generic*, meaning that a user should be abe to take some concrete facility and apply it to its own data structures.
Yes. I worry that if we took just the bottom layer (basic types) without any of the algorithms people would not be able to understand why I took the trouble to generalize.
The usefulness of the libraries is just the bait to get people to read the code and learn from it. Being useful is one of the stated requirements for any boost library, but you have a point. If the library is really cool in the way it is designed and implemented, then one could argue that its usefullness lies exactly
there.
These algorithms are of general usefulness to VLSI cad. They probably have applications in other fields (how many axis parallel rectangles do you see on your computer monitor every day?), but I can promise a great deal of interest will come from my industry. The primary problem with these algorithms is that it seems like an easy enough problem that everyone tries to solve it for themselves, but is actually hard enough that most people fail to do it right. I have just today learned of yet another such example from within Intel. I'm starting to loose count. That problem would be solved if there were a really good public domain implementation in a place like boost. Unfortunately, I have also learned that I may be forced to wait three months before being allowed to request at the department level that the source code be released. Once that is done, I will be allowed to hurry up and wait for the corporate level process. I'm afraid I can no longer be optimistic about how long it will take before I can upload the code. I'm working every angle I can think of, however. Luke
John Femiani wrote:
I also suspect that CGAL (which apparently is not as free as boost)
CGAL is modularized and each package has its own license. Many packages, like Basic Kernels, Number Types, 2D Polygons, etc are released under the LPGL: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html which is not as free as the boost license but it's close enough for most applications. Furthermore, CGAL is now open-source, which means everyone can participate. The process is similar to boost, except that is Editorial Board reviewed rather than peer-reviewed. For this reason I usually recommend people to contribute geometric libraries to CGAL rather than boost. But of course I'm biased as I am both a Boost developer and a CGAL developer. ----------- Dear Suto: Now that I finally understood what your library is about, would you consider CGAL as a home for it? AFAICT this stuff is not covered in the current CGAL offering. Feel free to contact me directly if would like to do that. One comment though, I would not present it as a "geometric library" since it focuses on one very particular class of geometry: overlapping AA rectrangles. In typical geometric computing a "(2D) polygon" is a sequence of points, while in your case is restricted to the overlay of axis-aligned rectangles. It is much easier for us if you pick less overloaded terms for your library and its elements, to avoid confusions. Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
Fernando Cacciola wrote:
John Femiani wrote:
I also suspect that CGAL (which apparently is not as free as boost)
CGAL is modularized and each package has its own license.
Many packages, like Basic Kernels, Number Types, 2D Polygons, etc are released under the LPGL:
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html
which is not as free as the boost license but it's close enough for most applications.
Furthermore, CGAL is now open-source, which means everyone can participate. The process is similar to boost, except that is Editorial Board reviewed rather than peer-reviewed. For this reason I usually recommend people to contribute geometric libraries to CGAL rather than boost. But of course I'm biased as I am both a Boost developer and a CGAL developer.
-----------
Dear Suto:
Now that I finally understood what your library is about, would you consider CGAL as a home for it? AFAICT this stuff is not covered in the current CGAL offering. Feel free to contact me directly if would like to do that.
One comment though, I would not present it as a "geometric library" since it focuses on one very particular class of geometry: overlapping AA rectrangles. In typical geometric computing a "(2D) polygon" is a sequence of points, while in your case is restricted to the overlay of axis-aligned rectangles. It is much easier for us if you pick less overloaded terms for your library and its elements, to avoid confusions.
Best
I admit that GTL is not a generic geometric library, it has limited scope. It is limited to rectilinear geometry, fixed precision. It took us years of development, refinement and brutal testing to get where we are. Certainly there is much more geometry out there, math has no boundaries. Our internal name is GTL and was using that name. Our main target is to make it available on boost and facilitate its adoption in other libraries. We are certainly open to suggestions and feedback. thanks Gyuszi
"Fernando Cacciola" <fernando_cacciola@hotmail.com> writes:
I also suspect that CGAL (which apparently is not as free as boost)
CGAL is modularized and each package has its own license.
Many packages, like Basic Kernels, Number Types, 2D Polygons, etc are released under the LPGL [...]
which is not as free as the boost license but it's close enough for most applications.
The problem is that taken as a whole, the CGAL license situation is a huge mess -- _most_ of the library seems to be under the ultra-obnoxious QPL, and there are inter-package "dependencies" that sometimes cause a LGPL'd CGAL package to more or less "depend" on a QPL'd package! For instance, the CGAL "surface subdivision" package, which is licensed under the LGPL, is template-parameterized with an underlying 3d polygon type -- however the appropriate CGAL 3d polygon type uses the QPL! I put "dependencies" in quotes, because the template parameterization means it's a "defacto" dependency rather than hard one. However, given the range of functionality used by the SS package, it doesn't look particularly trivial to replace the underlying polygon type with one's one code. I think many users that would be otherwise OK with the LGPL would be put off by this confusing situation, as I am.
Furthermore, CGAL is now open-source, which means everyone can participate. ... For this reason I usually recommend people to contribute geometric libraries to CGAL rather than boost.
I would never consider contributing to CGAL, nor using it, until they straighten out the licensing. -Miles -- In New York, most people don't have cars, so if you want to kill a person, you have to take the subway to their house. And sometimes on the way, the train is delayed and you get impatient, so you have to kill someone on the subway. [George Carlin]
Miles Bader wrote:
"Fernando Cacciola" <fernando_cacciola@hotmail.com> writes:
I also suspect that CGAL (which apparently is not as free as boost)
CGAL is modularized and each package has its own license.
Many packages, like Basic Kernels, Number Types, 2D Polygons, etc are released under the LPGL [...]
which is not as free as the boost license but it's close enough for most applications.
The problem is that taken as a whole, the CGAL license situation is a huge mess -- _most_ of the library seems to be under the ultra-obnoxious QPL, and there are inter-package "dependencies" that sometimes cause a LGPL'd CGAL package to more or less "depend" on a QPL'd package!
That's because the dual licensing scheme is new, so it might still need improvement, but also because in principle each package author chooses LGPL or QPL.
for instance, the CGAL "surface subdivision" package, which is licensed under the LGPL, is template-parameterized with an underlying 3d polygon type -- however the appropriate CGAL 3d polygon type uses the QPL!
This is clearly a problem but is fair to say the the problem exists precisely because the author of the that subdivision package wanted his code to be free (as far as LPGL goes), but it not up to him to decide the license for its dependencies. This is definitely something that should be reported (I'll do that).
I put "dependencies" in quotes, because the template parameterization means it's a "defacto" dependency rather than hard one. However, given the range of functionality used by the SS package, it doesn't look particularly trivial to replace the underlying polygon type with one's one code.
Right, it is not.
I think many users that would be otherwise OK with the LGPL would be put off by this confusing situation, as I am.
Of course. But I wasn't aware of it, and probably the Polyhedron author, and the Board, aren't either. I consider this a "licensing bug". It might be fixable.
Furthermore, CGAL is now open-source, which means everyone can participate. ... For this reason I usually recommend people to contribute geometric libraries to CGAL rather than boost.
I would never consider contributing to CGAL, nor using it, until they straighten out the licensing.
Fair enough. What would you propose? Please respond off list, I've stolen too much bandwidth already. Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
"Fernando Cacciola" <fernando_cacciola@hotmail.com> writes:
I think many users that would be otherwise OK with the LGPL would be put off by this confusing situation, as I am.
Of course. But I wasn't aware of it, and probably the Polyhedron author, and the Board, aren't either.
Ok. It's unfortunate that licensing is an issue, but it is.
I consider this a "licensing bug". It might be fixable.
It would be great if it was.
I would never consider contributing to CGAL, nor using it, until they straighten out the licensing.
Fair enough. What would you propose?
I think ultimately, any use of (or indirect dependency on) the QPL in core code is going to cause many people to avoid CGAL -- it's a widely reviled license and causes major practical problems. I would suggest that the only real solution is to relicense as much as possible -- and at least the lower-level core primitives -- under a more friendly license (GPL compatible, drop the restrictions on redistributing modified source). Obviously this requires cooperation from the authors, who might object, but I don't think CGAL's really going anywhere in the FOSS world unless they do. If that's not possible, I guess at least an easy-to-understand diagram showing the "effective" (including dependencies) licensing of each package in CGAL might at least help users be less confused. -Miles -- Quidquid latine dictum sit, altum viditur.
"Fernando Cacciola" <fernando_cacciola@hotmail.com> writes:
I also suspect that CGAL (which apparently is not as free as boost)
CGAL is modularized and each package has its own license.
Many packages, like Basic Kernels, Number Types, 2D Polygons, etc are released under the LPGL [...]
which is not as free as the boost license but it's close enough for most applications.
The problem is that taken as a whole, the CGAL license situation is a huge mess -- _most_ of the library seems to be under the ultra-obnoxious QPL, and there are inter-package "dependencies" that sometimes cause a LGPL'd CGAL package to more or less "depend" on a QPL'd package! For instance, the CGAL "surface subdivision" package, which is licensed under the LGPL, is template-parameterized with an underlying 3d polygon type -- however the appropriate CGAL 3d polygon type uses the QPL! I put "dependencies" in quotes, because the template parameterization means it's a "defacto" dependency rather than hard one. However, given the range of functionality used by the SS package, it doesn't look particularly trivial to replace the underlying polygon type with one's one code. I think many users that would be otherwise OK with the LGPL would be put off by this confusing situation, as I am.
Furthermore, CGAL is now open-source, which means everyone can participate. ... For this reason I usually recommend people to contribute geometric libraries to CGAL rather than boost.
I would never consider contributing to CGAL, nor using it, until they straighten out the licensing. -Miles -- In New York, most people don't have cars, so if you want to kill a person, you have to take the subway to their house. And sometimes on the way, the train is delayed and you get impatient, so you have to kill someone on the subway. [George Carlin]
participants (10)
-
Fernando Cacciola -
Joel de Guzman -
John Femiani -
Malte Clasen -
Michael Marcin -
Miles Bader -
Phil Endecott -
Simonson, Lucanus J -
Suto, Gyuszi -
Tom Brinkman