Segfault when convex decomposing Nef_polyhedron or infinite loop

CGAL / cgal

The public CGAL repository, see the README below

Other

5.02k stars 1.39k forks source link

Hi there, I was trying to run convex decomposition on the nef_polyhedron, but it's failed with a segfault or looped infinitely.

Issue Details

Error: signal 11:
./src/test/decompose_exe(_Z7handleri+0x30)[0x556edd1ae100]
/lib/x86_64-linux-gnu/libc.so.6(+0x46210)[0x7f11cd335210]
./src/test/decompose_exe(_ZN4CGAL22SNC_external_structureINS_17SNC_indexed_itemsENS_13SNC_structureINS_5EpeckES1_bEEE24build_external_structureEv+0x536)[0x556edd42db26]
./src/test/decompose_exe(_ZN4CGAL26External_structure_builderINS_16Nef_polyhedron_3INS_5EpeckENS_17SNC_indexed_itemsEbEEEclERNS4_10SNC_and_PLE+0x2c6)[0x556edd42e8d6]
./src/test/decompose_exe(_ZN4CGAL22convex_decomposition_3INS_16Nef_polyhedron_3INS_5EpeckENS_17SNC_indexed_itemsEbEEEEvRT_+0x13b9)[0x556edd4338d9]

I used gdb to check what caused the segfault and it's one of the iterators from here: https://github.com/CGAL/cgal/blob/c733c2a9874a9b47a03cbf2bfade32c0a2b51fee/Nef_3/include/CGAL/Nef_3/SNC_external_structure.h#L1320

Thread 1 "decompose_exe" received signal SIGSEGV, Segmentation fault.
0x000055555597da48 in CGAL::SNC_external_structure<CGAL::SNC_indexed_items, CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> >::build_external_structure (
    this=this@entry=0x7fffffffc940) at /home/szobov/dev/transformers/libigl/external/cgal/Nef_3/include/CGAL/Nef_3/SNC_external_structure.h:1345
1345          for (bool _circ_loop_flag = !::CGAL::is_empty_range(circ, end);
(gdb) 
(gdb) p circ
$1 = {<CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> > >, std::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> > > > >> = {node = 0x0}, <No data fields>}

I understand, that it's not the root of the problem, but just the consequences, but I hope it's can be useful to debug.

Source Code

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_3/SNC_indexed_items.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/convex_decomposition_3.h>

#include <igl/copyleft/cgal/mesh_to_polyhedron.h>
#include <igl/read_triangle_mesh.h>

#include <Eigen/Dense>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef Polyhedron::HalfedgeDS HalfedgeDS;
typedef Kernel::Point_3 Point;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Nef_polyhedron::Volume_const_iterator Volume_const_iterator;

int main(int argc, char *argv[])
{
    Eigen::MatrixXi face;
    Eigen::MatrixXd vert;
    igl::read_triangle_mesh("/tmp/broken_mesh1804289383.stl", vert, face);

    Polyhedron poly;
    igl::copyleft::cgal::mesh_to_polyhedron(vert, face, poly);
    Nef_polyhedron nef;
    nef = Nef_polyhedron(poly);

    CGAL::convex_decomposition_3(nef);

    return 0;
}

(I didn't compile it but seems to be valid) broken_mesh1804289383.stl.zip

Environment

Operating system (Linux, 64 bits):
Compiler: gcc (Ubuntu 9.3.0-17ubuntu1~20.04)
Release or debug mode: release
Specific flags used (if any):
CGAL version: 5.2.1 (I update CGAL directly to commit c733c2a9874a9b47a03cbf2bfade32c0a2b51fee)
Boost version: 1.71
Other libraries versions if used (Eigen, TBB, etc.): Eigen 3.3.7-2

Process 239893 launched: 'test_exe' (x86_64) Process 239893 stopped * thread #1, name = 'test_exe', stop reason = signal SIGSEGV: invalid address (fault address: 0x38) frame #0: 0x0000555555636cd3 test_exe`CGAL::SNC_FM_decorator<CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> >::determine_facet(this=0x00007fffffffd390, e=<unavailable>, MinimalEdge=size=1, FacetCycle=0x00007fffffffcbd0, Edge_of=size=4) const at SNC_FM_decorator.h:420:22 417 #endif 418 CGAL_assertion( e_below != SHalfedge_handle() ); 419 CGAL_NEF_TRACEN(" edge below " << debug(e_below)); -> 420 Halffacet_handle f = e_below->facet(); 421 if ( f != Halffacet_handle() ) return f; // has already a facet 422 // e_below also has no facet 423 f = determine_facet(e_below, MinimalEdge, FacetCycle, Edge_of); (lldb) thread backtrace * thread #1, name = 'test_exe', stop reason = signal SIGSEGV: invalid address (fault address: 0x38) * frame #0: 0x0000555555636cd3 test_exe`CGAL::SNC_FM_decorator<CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> >::determine_facet(this=0x00007fffffffd390, e=<unavailable>, MinimalEdge=size=1, FacetCycle=0x00007fffffffcbd0, Edge_of=size=4) const at SNC_FM_decorator.h:420:22 frame #1: 0x000055555565ef26 test_exe`CGAL::SNC_FM_decorator<CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> >::create_facet_objects(this=0x00007fffffffd390, plane_supporting_facet=<unavailable>, start=<unavailable>, end=<unavailable>) const at SNC_FM_decorator.h:646:22 frame #2: 0x000055555565fbe2 test_exe`CGAL::SNC_external_structure<CGAL::SNC_indexed_items, CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> >::categorize_facet_cycles_and_create_facets(this=0x00007fffffffd640) const at SNC_external_structure.h:1274:7 frame #3: 0x000055555566f48b test_exe`CGAL::SNC_external_structure<CGAL::SNC_indexed_items, CGAL::SNC_structure<CGAL::Epeck, CGAL::SNC_indexed_items, bool> >::build_external_structure(this=0x00007fffffffd640) at SNC_external_structure.h:1371:5 frame #4: 0x0000555555672fad test_exe`CGAL::Nef_polyhedron_3<CGAL::Epeck, CGAL::SNC_indexed_items, bool>::Nef_polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> >(CGAL::Polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> >&) [inlined] CGAL::Nef_polyhedron_3<CGAL::Epeck, CGAL::SNC_indexed_items, bool>::build_external_structure(this=<unavailable>) at Nef_polyhedron_3.h:352:5 frame #5: 0x0000555555672f8b test_exe`CGAL::Nef_polyhedron_3<CGAL::Epeck, CGAL::SNC_indexed_items, bool>::Nef_polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> >(this=0x00007fffffffd900, P=0x00007fffffffd920) at Nef_polyhedron_3.h:607 frame #6: 0x00005555555e8234 test_exe`main at test.cpp:29:9 frame #7: 0x00007ffff79640b3 libc.so.6`__libc_start_main + 243 frame #8: 0x00005555555e856e test_exe`_start + 46

CGAL / cgal