Better examples of `CGAL::extract_mean_curvature_flow_skeleton` to explicit the requirement for pure-triangle meshes

david-zwicker commented 7 years ago

I run into a segmentation fault when trying to extract the skeleton of some geometries. I generally deal with more complicated cases, but here is a simple example, where the algorithm fails: boxcubecc3.off.zip

Issue Details

I ran the program given below and receive the following result from gdb on my Linux system:

run boxcubecc3.off [Thread debugging using libthread_db enabled] Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1". Read geometry assuming OFF format: boxcubecc3.off Extract the skeleton

Program received signal SIGSEGV, Segmentation fault. 0x0000000000436348 in boost::graph_traits<CGAL::Polyhedron_3<CGAL::Simple_cartesian, CGAL::internal::Skel_polyhedron_items_3<CGAL::internal::In_place_list_iterator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > >, std::allocator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > > > > >, CGAL::HalfedgeDS_default, std::allocator > >::halfedge_descriptor CGAL::Euler::join_vertex<CGAL::Polyhedron_3<CGAL::Simple_cartesian, CGAL::internal::Skel_polyhedron_items_3<CGAL::internal::In_place_list_iterator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > >, std::allocator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > > > > >, CGAL::HalfedgeDS_default, std::allocator > >(boost::graph_traits<CGAL::Polyhedron_3<CGAL::Simple_cartesian, CGAL::internal::Skel_polyhedron_items_3<CGAL::internal::In_place_list_iterator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > >, std::allocator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > > > > >, CGAL::HalfedgeDS_default, std::allocator > >::halfedge_descriptor, CGAL::Polyhedron_3<CGAL::Simple_cartesian, CGAL::internal::Skel_polyhedron_items_3<CGAL::internal::In_place_list_iterator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > >, std::allocator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::I_Polyhedron_vertex<CGAL::HalfedgeDS_vertex_base<CGAL::HalfedgeDS_list_types<CGAL::Simple_cartesian, CGAL::I_Polyhedron_derived_items_3, std::allocator >, CGAL::Boolean_tag, CGAL::Point_3<CGAL::Simple_cartesian > > > > > > >, CGAL::HalfedgeDS_default, std::allocator >&) ()

Source Code

#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Mean_curvature_flow_skeletonization.h>

#include <CGAL/extract_mean_curvature_flow_skeleton.h>

#include <fstream>

typedef CGAL::Simple_cartesian<double>                        Kernel;
typedef Kernel::Point_3                                       Point;
typedef CGAL::Polyhedron_3<Kernel>                            Polyhedron;

typedef boost::graph_traits<Polyhedron>::vertex_descriptor    vertex_descriptor;

typedef CGAL::Mean_curvature_flow_skeletonization<Polyhedron> Skeletonization;
typedef Skeletonization::Skeleton                             Skeleton;

typedef Skeleton::vertex_descriptor                           Skeleton_vertex;
typedef Skeleton::edge_descriptor                             Skeleton_edge;

int main(int argc, char* argv[]) {

    if (argc < 2) {
        std::cout << "Input geometry must be given as first argument" << std::endl;
        return EXIT_FAILURE;
    }

    std::ifstream input(argv[1]);

    // read the input file
    std::cerr << "Read geometry assuming OFF format: " << argv[1] << std::endl;
    Polyhedron tmesh;
    input >> tmesh;

    // get the actual skeleton
    std::cerr << "Extract the skeleton" << std::endl;
    Skeleton skeleton;
    CGAL::extract_mean_curvature_flow_skeleton(tmesh, skeleton);

    // output some statistics  
    std::cout << "Number of vertices of the skeleton: "
            << boost::num_vertices(skeleton) << std::endl;
    std::cout << "Number of edges of the skeleton: " 
            << boost::num_edges(skeleton) << std::endl;

    return EXIT_SUCCESS;
}

Environment

I tried this in two different environments and got the same result for the attached geometry. However, for some geometries the skeleton could be determined on the Mac system, while it caused a SegFault on the Linux system.

System 1:

Operating system (Windows/Mac/Linux, 32/64 bits): Mac 64 Bits
Compiler: Clang 4.0.0
Release or debug mode: Release
Specific flags used (if any): -pipe -Os -std=c++11 -DNDEBUG
CGAL version: 4.9
Boost version: 1.59.0
Other libraries versions if used (Eigen, TBB, etc.): Eigen 3.3.3

otool -L skeleton gives

skeleton: /opt/local/lib/libmpfr.4.dylib (compatibility version 6.0.0, current version 6.5.0) /opt/local/lib/libgmp.10.dylib (compatibility version 14.0.0, current version 14.2.0) /opt/local/lib/libCGAL.12.dylib (compatibility version 12.0.0, current version 12.0.0) /opt/local/lib/libboost_thread-mt.dylib (compatibility version 0.0.0, current version 0.0.0) /opt/local/lib/libboost_system-mt.dylib (compatibility version 0.0.0, current version 0.0.0) /opt/local/lib/libboost_chrono-mt.dylib (compatibility version 0.0.0, current version 0.0.0) /opt/local/lib/libboost_date_time-mt.dylib (compatibility version 0.0.0, current version 0.0.0) /opt/local/lib/libboost_atomic-mt.dylib (compatibility version 0.0.0, current version 0.0.0) /usr/lib/libc++.1.dylib (compatibility version 1.0.0, current version 307.5.0) /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1238.51.1)

System 2:

Operating system (Windows/Mac/Linux, 32/64 bits): Linux Ubuntu 14.04
Compiler: Gnu 5.4.0
Release or debug mode: Debug
Specific flags used (if any): -frounding-math -std=c++11 -O3 -DNDEBUG
CGAL version: latest from GitHub (last pull on Apr 10); I also tried version 4.7 from the ubuntu repositories with the same effect
Boost version: 1.58.0
Other libraries versions if used (Eigen, TBB, etc.): Eigen 3.2.92

ldd skeleton gives

linux-vdso.so.1 => (0x00007ffe0dd30000) libmpfr.so.4 => /usr/lib/x86_64-linux-gnu/libmpfr.so.4 (0x00007f10ffb75000) libgmp.so.10 => /usr/lib/x86_64-linux-gnu/libgmp.so.10 (0x00007f10ff8f5000) libCGAL.so.13 => /home/dzwicker/user/programs/CGAL-current/cgal/lib/libCGAL.so.13 (0x00007f10ff6d2000) libboost_thread.so.1.58.0 => /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.58.0 (0x00007f10ff4ac000) libboost_system.so.1.58.0 => /usr/lib/x86_64-linux-gnu/libboost_system.so.1.58.0 (0x00007f10ff2a8000) libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f10ff08a000) libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f10fed08000) libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f10fe9ff000) libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f10fe7e8000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f10fe41f000) /lib64/ld-linux-x86-64.so.2 (0x000055cb6e20e000) librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007f10fe217000)

sloriot commented 7 years ago

The input must be a triangle mesh. Try calling CGAL::Polygon_mesh_processing::triangulate_faces() first.

david-zwicker commented 7 years ago

Thank you for the explanation. I agree that this is not a bug and also already documented in the respective sections. However, I suggest to add an explicit check to the examples in the documentation of the Triangulated Surface Mesh Skeletonization package. Adding the following code right after loading the mesh would help novice CGAL users like me:

    if (!tmesh.is_pure_triangle()) {
        std::cout << "Input geometry is not triangulated." << std::endl;
        return EXIT_FAILURE;
    }

lrineau commented 7 years ago

Thanks @david-zwicker. You are right about the need for better examples. Would you mind create a pull-request?

david-zwicker commented 7 years ago

@lrineau I'm afraid I don't know how to create pull-request. Is there a documentation for this somewhere?

afabri commented 7 years ago

We should do that systematically for all examples where this is requiredOn Apr 13, 2017 4:42 PM, David Zwicker notifications@github.com wrote:@lrineau I'm afraid I don't know how to create pull-request. Is there a documentation for this somewhere?

—You are receiving this because you are subscribed to this thread.Reply to this email directly, view it on GitHub, or mute the thread.

lrineau commented 7 years ago

This issue has been fixed by @janetournois (from GeometryFactory) in the PR #2060. I will be in CGAL-4.11-beta1, planned for mid-summer 2017.

CGAL / cgal