CGAL users discussion list

[Konstantinos Katrioplas <>]

Dear Sean,

PMP's corefine_and_compute_difference probably fails because there are self intersections in both meshes in the attached files. Maybe you could try removing them first using the functionality that is offered by PMP's repair.h file. You would need to include the header,

 #include <CGAL/Polygon_mesh_processing/repair.h>

and then add to your code something like that:

  PMP::remove_self_intersections(mesh_i);
  PMP::remove_self_intersections(mesh_j);
  PMP::corefine_and_compute_difference(mesh_i, mesh_j, mesh_out);

However, since repair.h is under development, please try this with version 4.12.

Regards,
Konstantinos

On 05/20/2018 09:29 PM, Sean Hardesty wrote:

Sebastien,

Back in December, you sent a function duplicate_non_manifold_vertices to be used prior to calling keep_largest_connected_components. It has mostly worked fine, but I have just recently stumbled across a case where it fails quickly and consistently: CGAL 4.11 segfaults (same thing with 4.11.1, 4.12) in the call to CGAL::Polygon_mesh_processing::corefine_and_compute_difference. I have attached .off files that were written immediately prior to the call where it segfaults. They aren't polygon soups, but they do have problems - looks like triangles are hanging off the corners, and weren't removed by prior calls to duplicate_non_manifold_vertices and keep_largest_connected_components. Do you have any suggestions about how to fix it?

    Thanks,

    Sean Hardesty

On Fri, Dec 15, 2017 at 2:02 AM, Sebastien Loriot (GeometryFactory) <> wrote:
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je], get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
  PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
  typedef boost::graph_traits<TriangleMesh> GT;
  typedef typename GT::vertex_descriptor vertex_descriptor;
  typedef typename GT::halfedge_descriptor halfedge_descriptor;

  boost::unordered_set<vertex_descriptor> vertices_handled;
  boost::unordered_set<halfedge_descriptor> halfedges_handled;

  std::size_t nb_new_vertices=0;

  std::vector<halfedge_descriptor> non_manifold_cones;
  BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
  {
    if (halfedges_handled.insert(h).second)
    {
      vertex_descriptor vd = target(h, tm);
      if ( !vertices_handled.insert(vd).second )
      {
        non_manifold_cones.push_back(h);
      }
      else
        set_halfedge(vd, h, tm);
      halfedge_descriptor start=opposite(next(h, tm), tm);
      h=start;
      do{
        halfedges_handled.insert(h);
        h=opposite(next(h, tm), tm);
      }while(h!=start);
    }
  }

  if (!non_manifold_cones.empty())  {
    BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
    {
      halfedge_descriptor start = h;
      vertex_descriptor new_vd = add_vertex(tm);
      ++nb_new_vertices;
      put(vpm, new_vd, get(vpm, target(h, tm)));
      set_halfedge(new_vd, h, tm);
      do{
        set_target(h, new_vd, tm);
        h=opposite(next(h, tm), tm);
      } while(h!=start);
    }
  }

  return nb_new_vertices;

}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) < <mailto:>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <
        <mailto:> <mailto:
        <mailto:>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss