Re: [boost] GSoC: "A Generic Geometric Library"
Dear Janek, As you already mentioned, the title of the proposal is misleading, as our focus here is not to write a whole geometric library, but a subset of it. I'm not sure whether the proposal is publicly available somewhere but I would like to include some part of it about the scope, hoping that would clear the doubt about the expectations from this project. " Regarding the specifics of this project, what I propose to do in a summer is a limited scope Boost library for 2D mesh and polygonal environments, where I will mainly concentrate on the combinatorial information and primitive geometric operations. Thus the proposed library should more aptly be called Boost.2Dmesh than Boost.Geometry. Note that there would very likely be comments as to the incompleteness of such a "geometry" library, since I will not cover application domains like windows / GUI, computer vision, computer graphics (beyond the simple 2D subdivision), etc. By purposely limiting myself to the scope described above, I would provide a foundation for representing and manipulating planar subdivisions which is already a huge help for people writing geometric applications. It is a very common task and having both a representation and generic algorithms (which can adapt to user representation as well) suits the design principle of generic libraries very well. " Best, huseyin Janek Kozicki <janek_listy <at> wp.pl> writes:
The link from http://code.google.com/soc/boost/about.html states:
"Programming geometric algorithms, even the most trivial ones, may require detailed knowledge about the problem because of the degenerate cases that frequently occur in practice. Moreover, geometric algorithms are full of case analysis and quite error-prone to program, and can get fairly sophisticated in order to improve the asymptotic performance.
The main motivation of this proposal is to develop an easy-to-use but also high quality (both in software engineering and in algorithmic content) geometric library, sharing the same design principles as the C++ STL, which is generic and extendible. My main focus will be on design of generic algorithms for navigating and manipulating 2D subdivisions."
I am worried. The lenghty discussions about geometric library spanned several years till now on this mailing list. Similarly as with Boost.Units library everyone had different expectations.
I strongly encourage the authors to change the name of this library (similarly as "math toolkit" is suggested to be renamed into "statistics toolkit"), or to change its focus.
"2D subdivisions" is not a thing that I'd be looking for inside a "generic geometric library".
Dear Huseyin,
Dear Janek,
" Regarding the specifics of this project, what I propose to do in a summer is a limited scope Boost library for 2D mesh and polygonal environments, where I will mainly concentrate on the combinatorial information and primitive geometric operations. Thus the proposed library should more aptly be called Boost.2Dmesh than Boost.Geometry. Note that there would very likely be comments as to the incompleteness of such a "geometry" library, since I will not cover application domains like windows / GUI, computer vision, computer graphics (beyond the simple 2D subdivision), etc. By purposely limiting myself to the scope described above, I would provide a foundation for representing and manipulating planar subdivisions which is already a huge help for people writing geometric applications. It is a very common task and having both a representation and generic algorithms (which can adapt to user representation as well) suits the design principle of generic libraries very well. "
Then I assume you will present the mesh as a form of graph and build it on top of the Boost.Graph library, where the geometric embedding is realized trough graph properties. In that case though, Boost.MeshGraph is probably more descriptive. Btw, what is the 2D? The topology or the geometry? Or both? Best Fernando Cacciola
Dear Fernando, The implementation will be based on half-edge scheme. However by using Boost.Intrusive adapters, it would be possible for our algorithms to use the BGL representations as well. When talking about the 2D we mainly talk about the combinatorial information, so I'll say its the topology (if this is what you mean by topology). Thank you (and others), its really great to get this much interest from the community. huseyin On 4/13/07, Fernando Cacciola <fernando_cacciola@hotmail.com> wrote:
Dear Huseyin,
Dear Janek,
" Regarding the specifics of this project, what I propose to do in a summer is a limited scope Boost library for 2D mesh and polygonal environments, where I will mainly concentrate on the combinatorial information and primitive geometric operations. Thus the proposed library should more aptly be called Boost.2Dmesh than Boost.Geometry. Note that there would very likely be comments as to the incompleteness of such a "geometry" library, since I will not cover application domains like windows / GUI, computer vision, computer graphics (beyond the simple 2D subdivision), etc. By purposely limiting myself to the scope described above, I would provide a foundation for representing and manipulating planar subdivisions which is already a huge help for people writing geometric applications. It is a very common task and having both a representation and generic algorithms (which can adapt to user representation as well) suits the design principle of generic libraries very well. "
Then I assume you will present the mesh as a form of graph and build it on top of the Boost.Graph library, where the geometric embedding is realized trough graph properties.
In that case though, Boost.MeshGraph is probably more descriptive.
Btw, what is the 2D? The topology or the geometry? Or both?
Best
Fernando Cacciola
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Dear Fernando,
The implementation will be based on half-edge scheme. However by using Boost.Intrusive adapters, it would be possible for our algorithms to use the BGL representations as well.
When talking about the 2D we mainly talk about the combinatorial information, so I'll say its the topology (if this is what you mean by topology).
Thank you (and others), its really great to get this much interest from the community.
huseyin
Hey if you are interested, there is a library I explored before (www.openmesh.org) and of course I think CGAL has a half-edge (or maybe double-edge) mesh. I think that it would be good if you can at least model the BGL Concepts, so that the BGL algorithms can be applied to the mesh. There is a much more generic concept than half-edge (HE) meshes called a 'lath' mesh (http://graphics.idav.ucdavis.edu/publications/print_pub?pub_id=357). Unfortunately I only read about this (and several other papers) after learning the hard way that a HE mesh does not suit every purpose. This, or something like it, is important to me because in many scenarios a mesh is not always manifold all the time, especially if you wish to maintain the connectivity as you operate on it by adding and removing faces. A HE mesh can not adequately represent a non manifold mesh, such as would result when you deleted two non-adjacent triangles from a vertex and filled-in the gap between them with a single polygon for example. In fact that type of operation can be EXTREMELY tricky if I remember because the corners at a vertex on more than one hole have no ordering between them, and you have to carefully consider legitimate ways to shuffle the wedges (connected sets of corners) whenever a new cell is added in order to maintain the validity of the mesh, provided you wish to maintain the connectivity-data structure as faces are added and deleted. In the paper I linked-to above a 'lathe' is defined at each _corner_ rather than at each edge. They present a concept for representing connectivity that generalizes several other data structures (including HE), and they discuss issues related to how a lath representation impacts boundary traversal or non-manifold edges. What is awesome is that I think this same concept extends to 3-manifold meshes as well (but I don't know if the authors ever developed that). Even if you do not extend your mesh library to 3D, I hope that you think about how it would be done and make sure the library is flexible enough to grow in that direction. This is another paper, which actually deals with both 2D & 3D meshes, but it nicely describes the kinds of issues I hope can be dealt with (http://portal.acm.org/citation.cfm?id=882380) I gather from the boost discussions that nobody has yet even settled on a boost-approved point & vector concept or class (uBlas has c_vector, and gil has point2 but that is kind of internal to the library and not intended to be for general use). Would this library include those? John Femiani _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Dear John, Thanks for the pointers and papers, I'll check them for sure. A standard point concept is not in the plan (at least for the summer project). As geometric objects are widely used, the expectations also varies a lot, so we had to limit ourselves in terms of features. Best, huseyin On 4/14/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
Dear Fernando,
The implementation will be based on half-edge scheme. However by using Boost.Intrusive adapters, it would be possible for our algorithms to use the BGL representations as well.
When talking about the 2D we mainly talk about the combinatorial information, so I'll say its the topology (if this is what you mean by topology).
Thank you (and others), its really great to get this much interest from the community.
huseyin
Hey if you are interested, there is a library I explored before (www.openmesh.org) and of course I think CGAL has a half-edge (or maybe double-edge) mesh. I think that it would be good if you can at least model the BGL Concepts, so that the BGL algorithms can be applied to the mesh.
There is a much more generic concept than half-edge (HE) meshes called a 'lath' mesh (http://graphics.idav.ucdavis.edu/publications/print_pub?pub_id=357). Unfortunately I only read about this (and several other papers) after learning the hard way that a HE mesh does not suit every purpose. This, or something like it, is important to me because in many scenarios a mesh is not always manifold all the time, especially if you wish to maintain the connectivity as you operate on it by adding and removing faces. A HE mesh can not adequately represent a non manifold mesh, such as would result when you deleted two non-adjacent triangles from a vertex and filled-in the gap between them with a single polygon for example. In fact that type of operation can be EXTREMELY tricky if I remember because the corners at a vertex on more than one hole have no ordering between them, and you have to carefully consider legitimate ways to shuffle the wedges (connected sets of corners) whenever a new cell is added in order to maintain the validity of the mesh, provided you wish to maintain the connectivity-data structure as faces are added and deleted.
In the paper I linked-to above a 'lathe' is defined at each _corner_ rather than at each edge. They present a concept for representing connectivity that generalizes several other data structures (including HE), and they discuss issues related to how a lath representation impacts boundary traversal or non-manifold edges. What is awesome is that I think this same concept extends to 3-manifold meshes as well (but I don't know if the authors ever developed that). Even if you do not extend your mesh library to 3D, I hope that you think about how it would be done and make sure the library is flexible enough to grow in that direction. This is another paper, which actually deals with both 2D & 3D meshes, but it nicely describes the kinds of issues I hope can be dealt with (http://portal.acm.org/citation.cfm?id=882380)
I gather from the boost discussions that nobody has yet even settled on a boost-approved point & vector concept or class (uBlas has c_vector, and gil has point2 but that is kind of internal to the library and not intended to be for general use). Would this library include those?
John Femiani
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi John,
I think CGAL has a half-edge (or maybe double-edge) mesh.
Right, CGAL offers a halfedge data-structure. Furthermore, the next CGAL version will offer a BGL package that allows users to pass combinatorial data structures (polyhedrons (HE), triangulations, etc), as-is, to BGL algorithms (using external adapatation), or to implement new structure-independent algorithms following the BGL paradigm, like the forthcoming Surface Mesh Simplification package.
I think that it would be good if you can at least model the BGL Concepts, so that the BGL algorithms can be applied to the mesh.
I would consider this a requirement.
There is a much more generic concept than half-edge (HE) meshes called a 'lath' mesh
Interesting. I was just in the need for such a reference, thank you :)
I gather from the boost discussions that nobody has yet even settled on a boost-approved point & vector concept or class (uBlas has c_vector, and gil has point2 but that is kind of internal to the library and not intended to be for general use). Would this library include those?
IMHO, given that these primitives spread a few computing domains and everyone has its own idea about it, I would refrain from trying to "formalize" them in the current library. Instead, I would make sure the library works fine with your prefered point/vector type. I would just include a simple proof-of-concept primitive. Best -- ------ Fernando Cacciola SciSoft http://certuscode.wordpress.com http://fcacciola.50webs.com http://fcacciola.wordpress.com
Fernando: you re right on all counts, those are our intentions... -- Hervé Sent from my BlackBerry® wireless handheld Please excuse misspellings and typos -----Original Message----- From: Fernando Cacciola <fernando_cacciola@hotmail.com> Date: Mon, 16 Apr 2007 09:29:54 To:boost@lists.boost.org Subject: Re: [boost] GSoC: "A Generic Geometric Library" Hi John,
I think CGAL has a half-edge (or maybe double-edge) mesh.
Right, CGAL offers a halfedge data-structure. Furthermore, the next CGAL version will offer a BGL package that allows users to pass combinatorial data structures (polyhedrons (HE), triangulations, etc), as-is, to BGL algorithms (using external adapatation), or to implement new structure-independent algorithms following the BGL paradigm, like the forthcoming Surface Mesh Simplification package.
I think that it would be good if you can at least model the BGL Concepts, so that the BGL algorithms can be applied to the mesh.
I would consider this a requirement.
There is a much more generic concept than half-edge (HE) meshes called a 'lath' mesh
Interesting. I was just in the need for such a reference, thank you :)
I gather from the boost discussions that nobody has yet even settled on a boost-approved point & vector concept or class (uBlas has c_vector, and gil has point2 but that is kind of internal to the library and not intended to be for general use). Would this library include those?
IMHO, given that these primitives spread a few computing domains and everyone has its own idea about it, I would refrain from trying to "formalize" them in the current library. Instead, I would make sure the library works fine with your prefered point/vector type. I would just include a simple proof-of-concept primitive. Best -- ------ Fernando Cacciola SciSoft http://certuscode.wordpress.com http://fcacciola.50webs.com http://fcacciola.wordpress.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Herve, I understand that a 'point' class is quite unnecessary if you are focusing on a purely topological mesh data structure, and that the class should be templatized on the point type as should any class which requires a point in boost. Of course if quaternion's make it into boost I do not see why points should not; both assume a similar coordinate system and have well defined semantics, closely tied with geometric vecters, in affine geometry. Perhaps I should start a thread about 'val_tuple', or wait until something the likes of wykobi makes a submission :) I don't really know my way around boost yet wrt SoC stuff; Is there a wiki up for this SoC project on googlecode or something so I can keep up to date with your work and also maybe hassle you guys about it in a friendly way? John -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Herve Bronnimann Sent: Monday, April 16, 2007 6:45 AM To: boost@lists.boost.org Subject: Re: [boost] GSoC: "A Generic Geometric Library" Fernando: you re right on all counts, those are our intentions... -- Hervé Sent from my BlackBerry® wireless handheld Please excuse misspellings and typos -----Original Message----- From: Fernando Cacciola <fernando_cacciola@hotmail.com> Date: Mon, 16 Apr 2007 09:29:54 To:boost@lists.boost.org Subject: Re: [boost] GSoC: "A Generic Geometric Library" Hi John,
I think CGAL has a half-edge (or maybe double-edge) mesh.
Right, CGAL offers a halfedge data-structure. Furthermore, the next CGAL version will offer a BGL package that allows users to pass combinatorial data structures (polyhedrons (HE), triangulations, etc), as-is, to BGL algorithms (using external adapatation), or to implement new structure-independent algorithms following the BGL paradigm, like the forthcoming Surface Mesh Simplification package.
I think that it would be good if you can at least model the BGL Concepts, so that the BGL algorithms can be applied to the mesh.
I would consider this a requirement.
There is a much more generic concept than half-edge (HE) meshes called a 'lath' mesh
Interesting. I was just in the need for such a reference, thank you :)
I gather from the boost discussions that nobody has yet even settled on a boost-approved point & vector concept or class (uBlas has c_vector, and gil has point2 but that is kind of internal to the library and not intended to be for general use). Would this library include those?
IMHO, given that these primitives spread a few computing domains and everyone has its own idea about it, I would refrain from trying to "formalize" them in the current library. Instead, I would make sure the library works fine with your prefered point/vector type. I would just include a simple proof-of-concept primitive. Best -- ------ Fernando Cacciola SciSoft http://certuscode.wordpress.com http://fcacciola.50webs.com http://fcacciola.wordpress.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
John Femiani wrote:
I don't really know my way around boost yet wrt SoC stuff; Is there a wiki up for this SoC project on googlecode or something so I can keep up to date with your work and also maybe hassle you guys about it in a friendly way?
There will be and students will be a wiki and svn code repository at some point in the future. In the meantime you should continue discussions here -- note that 'actual work' on the SoC projects doesn't really begin until end of May. The current interim period is for students to get introduced to the community, get to know their mentors, and work on project scope...exactly what you are up to now :-) Jeff
Wrt scope: Will this library include an algorithms specific to tesselations -- such as computing the dual mesh (a simple one) or subdivision, decimation, parameterization, triangulation, etc.? John -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeff Garland Sent: Monday, April 16, 2007 9:45 AM To: boost@lists.boost.org Subject: Re: [boost] GSoC: "A Generic Geometric Library" John Femiani wrote:
I don't really know my way around boost yet wrt SoC stuff; Is there a wiki up for this SoC project on googlecode or something so I can keep up to date with your work and also maybe hassle you guys about it in a friendly way?
There will be and students will be a wiki and svn code repository at some point in the future. In the meantime you should continue discussions here -- note that 'actual work' on the SoC projects doesn't really begin until end of May. The current interim period is for students to get introduced to the community, get to know their mentors, and work on project scope...exactly what you are up to now :-) Jeff _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
John Femiani wrote:
Wrt scope:
Will this library include an algorithms specific to tesselations -- such as computing the dual mesh (a simple one) or subdivision, decimation, parameterization, triangulation, etc.?
Huseyin - perhaps you can post your entire proposal somewhere? That might make the discussion easier. Jeff
Yes, I was wandering if the proposal already exists online somewhere. I guess not, so here it is: http://cis.poly.edu/~hakcan01/projects/hdstl.txt and these are the citations within the proposal: [1] Herve Bronnimann. Designing and implementing a general purpose half-edge data structure. Proc. 5th International Workshop on Algorithm Engineering (WAE), Aarhus, Denmark, LNCS 2141, G. Brodal, D. Frigioni, A. Marchetti-Spaccamela (Eds.), Springer Verlag, 2001, pp. 51-66. [4] Herve Bronnimann. Online documentation for HDSTL Framework. http://geometry.poly.edu/HDSTL/doc/hdstl/hdstl_introduction.htm huseyin On 4/16/07, Jeff Garland <jeff@crystalclearsoftware.com> wrote:
John Femiani wrote:
Wrt scope:
Will this library include an algorithms specific to tesselations -- such as computing the dual mesh (a simple one) or subdivision, decimation, parameterization, triangulation, etc.?
Huseyin - perhaps you can post your entire proposal somewhere? That might make the discussion easier.
Jeff _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Dear Huseyin,
Dear Fernando,
The implementation will be based on half-edge scheme.
I figured.
However by using Boost.Intrusive adapters,
Oh. Do you meant that the use of intrusive smart pointers will be hardcoded? Could you handle that generically? allowing users to use whatever smart-pointer or handle/body techinque they choose?
it would be possible for our algorithms to use the BGL representations as well.
I'm curious about why you relate intrusive pointers with the BGL. Can you elaborate?
When talking about the 2D we mainly talk about the combinatorial information, so I'll say its the topology (if this is what you mean by topology).
Right. Best ------ Fernando Cacciola SciSoft http://certuscode.wordpress.com http://fcacciola.50webs.com http://fcacciola.wordpress.com
Fernando: here you are misunderstanding: we're not referring to intrusive smart pointers, but intrusive data structure (recently submitted by Ion Gaztanaga). Essentially, intrusive DS is a way to provide algorithms on a legacy data structure (by decoupling access to the fundamental pointers inside the nodes), which is what we want here. -- Herve Bronnimann hervebronnimann@mac.com On Monday, April 16, 2007, at 08:15AM, "Fernando Cacciola" <fernando_cacciola@hotmail.com> wrote:
Dear Huseyin,
Dear Fernando,
The implementation will be based on half-edge scheme.
I figured.
However by using Boost.Intrusive adapters,
Oh. Do you meant that the use of intrusive smart pointers will be hardcoded? Could you handle that generically? allowing users to use whatever smart-pointer or handle/body techinque they choose?
it would be possible for our algorithms to use the BGL representations as well.
I'm curious about why you relate intrusive pointers with the BGL. Can you elaborate?
When talking about the 2D we mainly talk about the combinatorial information, so I'll say its the topology (if this is what you mean by topology).
Right.
Best
------ Fernando Cacciola SciSoft
http://certuscode.wordpress.com http://fcacciola.50webs.com http://fcacciola.wordpress.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Herve Bronnimann wrote:
Fernando: here you are misunderstanding: we're not referring to intrusive smart pointers, but intrusive data structure (recently submitted by Ion Gaztanaga). Essentially, intrusive DS is a way to provide algorithms on a legacy data structure (by decoupling access to the fundamental pointers inside the nodes), which is what we want here.
Ha yes, I got it exactly that much wrong ;) I guess is time to look into Boost.Intrusive then :) Best Fernando
participants (5)
-
Fernando Cacciola -
Herve Bronnimann -
Huseyin Akcan -
Jeff Garland -
John Femiani