Re: [boost] GSoC: "A Generic Geometric Library"

From: John Femiani (JOHN.FEMIANI_at_[hidden])
Date: 2007-04-14 03:49:03

> 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