CGAL users discussion list

["J.L.M." <>]

I have been writing some programs that use the Nef_polyhedron_3 and
Minkowski_sum_3 portions of the CGAL library. I have discovered a number 
of assertions with various input shapes. The attached backtrace shows 
one example problem. I have also attached a small example program, and 
the input shapes. The l-shape is shown in the attached jpeg file.

This problem shows up in both CGAL 3.7 and 3.6.1. I am using GCC 4.5.1
on Arch Linux with kernel version 2.6.36.

I think this is a bug, since it does not occur with other input shapes. 
I would be very grateful if someone can help me fix it since the 
Minkowski_sum_3 is essential to my research.

Thank you for your time.

Jason M'Sadoques

OFF
8 6 0
1.000000 1.000000 -1.000000
1.000000 -1.000000 -1.000000
-1.000000 -1.000000 -1.000000
-1.000000 1.000000 -1.000000
1.000000 1.000000 1.000000
1.000000 -1.000000 1.000000
-1.000000 -1.000000 1.000000
-1.000000 1.000000 1.000000
4 3 2 1 0
4 5 6 7 4
4 1 5 4 0
4 2 6 5 1
4 3 7 6 2
4 7 3 0 4

Attachment: l_shape.jpg
Description: JPEG image

OFF
16 14 0
1.000000 -1.000000 1.000000
1.000000 -1.000000 -1.000000
-1.000000 -1.000000 -1.000000
-1.000000 -1.000000 1.000000
1.000000 1.000000 1.000000
1.000000 1.000000 -1.000000
-1.000000 1.000000 -1.000000
-1.000000 1.000000 1.000000
-1.000000 3.000000 1.000000
-1.000000 3.000000 -1.000000
1.000000 3.000000 -1.000000
1.000000 3.000000 1.000000
3.000000 3.000000 1.000000
3.000000 3.000000 -1.000000
3.000000 1.000000 -1.000000
3.000000 1.000000 1.000000
4 3 2 1 0
4 1 5 4 0
4 2 6 5 1
4 3 7 6 2
4 7 3 0 4
4 8 9 6 7
4 9 10 5 6
4 11 8 7 4
4 10 9 8 11
4 12 13 10 11
4 15 12 11 4
4 13 14 5 10
4 14 15 4 5
4 13 12 15 14

/* This program shows the bug
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: Ntmp.is_valid()
File: /import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.6.1/include/CGAL/Minkowski_sum_3/bipartite_nary_union_sorted_combined.h
Line: 222
Aborted
*/

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/minkowski_sum_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/OFF_to_nef_3.h>
#include <fstream>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;

int main(int argc, char* argv[])
{
  Nef_polyhedron_3 container;
  std::ifstream file_stream("l_shape.off");
  int unhandled_facets=CGAL::OFF_to_nef_3(file_stream, container);
  file_stream.close();
  file_stream.clear();
  file_stream.open("cube.off");
  Nef_polyhedron_3 object;
  unhandled_facets=CGAL::OFF_to_nef_3(file_stream, object);

  Nef_polyhedron_3 container_boundary(container.boundary());
  Nef_polyhedron_3 result=container-CGAL::minkowski_sum_3(container_boundary, object);
  return(0);
}

jlm@mcp:~/school/masters_thesis/code
 146> gdb ./bug_ntmp_invalid 
GNU gdb (GDB) 7.2
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-unknown-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /usr/src/jlmcode/bug_ntmp_invalid...done.
(gdb) run
Starting program: /usr/src/jlmcode/bug_ntmp_invalid 
[Thread debugging using libthread_db enabled]
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: Ntmp.is_valid()
File: 
/import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.7/include/CGAL/Minkowski_sum_3/bipartite_nary_union_sorted_combined.h
Line: 222

Program received signal SIGABRT, Aborted.
0x00007ffff5a22595 in raise () from /lib/libc.so.6
(gdb) bt
#0  0x00007ffff5a22595 in raise () from /lib/libc.so.6
#1  0x00007ffff5a23a16 in abort () from /lib/libc.so.6
#2  0x00007ffff62a3ded in __gnu_cxx::__verbose_terminate_handler() () from 
/usr/lib/libstdc++.so.6
#3  0x00007ffff62a2006 in ?? () from /usr/lib/libstdc++.so.6
#4  0x00007ffff62a2033 in std::terminate() () from /usr/lib/libstdc++.so.6
#5  0x00007ffff62a213e in __cxa_throw () from /usr/lib/libstdc++.so.6
#6  0x00007ffff6e0760c in CGAL::assertion_fail (expr=0xcc5b6e 
"Ntmp.is_valid()", 
    file=0xcc5ab0 
"/import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.7/include/CGAL/Minkowski_sum_3/bipartite_nary_union_sorted_combined.h",
 line=222, msg=0xcc4fc0 "")
    at 
/import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.7/src/CGAL/assertions.cpp:116
#7  0x0000000000ad9cc0 in 
CGAL::bipartite_nary_union_sorted_combined<CGAL::Nef_polyhedron_3<CGAL::Lazy_kernel<CGAL::Simple_cartesian<CGAL::Gmpq>
 > > > (N0=..., N1=...)
    at 
/import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.7/include/CGAL/Minkowski_sum_3/bipartite_nary_union_sorted_combined.h:222
#8  0x0000000000ad4674 in 
CGAL::minkowski_sum_3<CGAL::Nef_polyhedron_3<CGAL::Lazy_kernel<CGAL::Simple_cartesian<CGAL::Gmpq>
 > > > (N0=..., N1=...)
    at 
/import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.7/include/CGAL/minkowski_sum_3.h:56
#9  0x0000000000ace1f0 in main (argc=1, argv=0x7fffffffd678)
    at 
/import/lightcycle/home/jlm/school/masters_thesis/code/bug_ntmp_invalid.cpp:34