CGAL users discussion list

[Richard Downe <>]

> The export to polyhedron induces a dummy triangulation of the facets.
> This means that the very long edges comes from the fact that in the
> original mesh you have long quad facets.
This I have a hard time believing.  My input surfaces are all pure 
triangle surfaces, where each rectangle from the structured grid is 
bisected into 2 right triangles.  They're evenly spaced, and only 
suboptimal at the end-caps, where I just triangulate around a single 
center point.

Looking closely at the flow extensions, which are where the skinny long 
triangles emerge, I see occasional remnants of my original surface in 
triangles scattered about in odd places.  The flow extensions, which is 
the only place this ever crops up, are functionally "straight-pipe" 
models, so that they could properly be represented by a very small 
number of long skinny triangles, as they have no curvature in the 
longitudinal direction, or are "flat" in the topological sense of a 
cylinder.  I'm convinced that the NEF code pares down the number of 
triangles based on this "flatness".

> One solution to simplify the boolean operation step is to first remesh
> your input and then do the union. That way I'm quite sure you are going
> to remove the degenerate triangle problem.
If my hypothesis regarding the reason why the long skinny triangles 
appear is correct, I'm not certain this will solve the problem. Though I 
suppose the fact that the points will no longer be arranged along a grid 
of parallel lines may dissuade the NEF code from rearranging them so.  
Nonetheless, I'm running low on options; I will give it a try and report 
back.

Thanks.
-rd

> Sebastien.
>
> On 10/25/2012 01:31 AM, Richard Downe wrote:
> > Couldn't get it to work right manipulating the iterators directly, but I
> > took your original advice, used the triangulated surface mesh
> > simplification stuff (I used the edge_length cost, and set the stopping
> > condition to 0.99*nEdges).
> >
> > This completely eliminates the degenerate triangles I had with
> > coincident points (I'm able to feed the .off intermediate output into my
> > program for building STL files without errors/zero-valued normals being
> > detected).
> >
> > Unfortunately, this surface is still stubbornly refusing remeshing. I've
> > attached a dropbox link to the .off output (post-surface simplification,
> > pre-remeshing) on the off chance that something about it might catch
> > your eye.
> >
> > (The really long edges at the flow extensions are not my doing -- these
> > invariably appear *post* Nef_polyhedron.)
> >
> > Thanks.
> > -rd
> >
> > http://dl.dropbox.com/u/66958528/cgal.off
> >
> > On 10/24/2012 08:22 AM, Sebastien Loriot (GeometryFactory) wrote:
> > > On 10/24/2012 03:18 PM, Richard Downe wrote:
> > > > I'll take a look at that.
> > > > Last night I wrote a fairly basic block of code that followed the
> > > > halfedge_iterator from halfedge_begin() to halfedge_end(), calling
> > > > join_vertex() any time the squared distance between two was smaller 
> > > > than
> > > > numeric_limits<float>::epsilon().
> > > > It did a fine job of pruning degenerate edges, but never converged 
> > > > (spit
> > > > out a list of a dozen or so pruned edges, but ran all night at 100% 
> > > > cpu
> > > > with no change in memory usage).
> > > >
> > > > So my assumption is that by calling join_vertex on a running loop I'm
> > > > breaking something, or these iterators never converge somehow. Am I
> > > > doing this wrong?
> > > I guess the iterator became invalid. Joining two vertices means
> > > deleting a pair of halfedges.
> > > If you ++ the iterator before joining it should be fine as the
> > > underlying data structure is a list by default.
> > >
> > > Note that you might need to do this loop several time as you could
> > > have cascaded collapse with such a method.
> > >
> > > Sebastien.
> > >
> > > > -rd
> > > >
> > > > On 10/24/2012 02:16 AM, Sebastien Loriot (GeometryFactory) wrote:
> > > > > You can try using the edge simplification algorithm [1]
> > > > > There is an example given in this thread (second post) [2]
> > > > >
> > > > > Let us know if this does not solve the problem.
> > > > >
> > > > > Sebastien.
> > > > >
> > > > > [1]
> > > > > http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Surface_mesh_simplification/Chapter_main.html 
> > > > >
> > > > >
> > > > >
> > > > > [2]
> > > > > http://cgal-discuss.949826.n4.nabble.com/understanding-edge-collapse-tt3248855.html 
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > On 10/24/2012 01:51 AM, Richard Downe wrote:
> > > > > > I have a program that uses Nef_Polyhedron_3 to merge several 
> > > > > > disjoint
> > > > > > structured grids, and then remeshes the surface using a delaunay
> > > > > > triangulation. Out of several surfaces I'm preparing, one has
> > > > > > stubbornly
> > > > > > refused to mesh. After a day or so of tweaking the parameters, I
> > > > > > generated .off files to permit me to visualize the intermediate
> > > > > > surface
> > > > > > and troubleshoot.
> > > > > >
> > > > > > In examining the .off version of the troublesome surface, I noticed
> > > > > > that
> > > > > > there are several degenerate triangles (e.g., 2 coincident
> > > > > > vertices, and
> > > > > > therefore a zero-valued normal). I'm assuming this has to do with
> > > > > > distances in the EPECK kernel that are too small to represent in the
> > > > > > EPICK kernel, which therefore get rounded off.
> > > > > >
> > > > > > My question is this: does a filter exist which can remove these
> > > > > > triangles *prior* to casting the polyhedron to an EPICK kernel? Or
> > > > > > am I
> > > > > > on my own (e.g., either filtering the inexact kernel version and
> > > > > > simply
> > > > > > erasing the degenerate triangles, or alternately, filtering the 
> > > > > > exact
> > > > > > one and merging any triangle with a sufficiently high aspect ratio
> > > > > > with
> > > > > > an adjacent triangle in the hopes of avoiding degeneracy post-cast)?
> > > > > >
> > > > > > Any help would be very much appreciated.
> > > > > >
> > > > > > -Richard