CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 10/25/2012 07:35 PM, Richard Downe wrote:
> > 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".
In that case, I bet on that one too.

> > 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.
In the meantime, if you provide me input files (in private message or
dropbox) with the list of Boolean operations, I can give another method
a try.

Sebastien.

> 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