CGAL users discussion list

[Bernhard Kornberger <>]

I've encountered a bug in the 3-dimensional Regular Triangulation:

CGAL 3.3:
typedef CGAL::Regular_triangulation_filtered_traits_3<K> RegtrTraits;
typedef CGAL::Regular_triangulation_3<RegtrTraits> Regular_triangulation;


Starting my software with:

./minkowski -i input1 -j input2

...I get this output:

############################

Starting All...
Starting PowerDiagram Construction...
Reading input1
Number of spheres: 125
Reading input2
Number of spheres: 46
Triangulator: inserting 8 bounding spheres
lower=-2396.4, upper=2595.59
a
b
c
d
e
f
g
h
Number of spheres to be visualized in union1.list: 125
Number of spheres to be visualized in union2.list: 46
Time for PowerDiagram Construction: [2.2 s]

Starting Postprocessing...

****** Starting the postprocessing of 2213 spheres, tolerance=1 *********

CGAL error: assertion violation!
Expr: !(i>s)
File: /opt/CGAL330/include/CGAL/Interval_nt.h
Line: 77
Explanation: Variable used before being initialized (or CGAL bug)
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: !(i>s)
File: /opt/CGAL330/include/CGAL/Interval_nt.h
Line: 77
Explanation:  Variable used before being initialized (or CGAL bug)
Aborted (core dumped)

############################





Starting the Software in valgrind:

valgrind ./minkowski -i input1 -j input2

...it crashes even earlier:


############################
/usr/bin/g++ -pg -I../../include -Wall -frounding-math 
'-I/opt/CGAL330/include' -I/usr/include/qt3  -O3   -c Triangulator.cpp
/usr/bin/g++   -o minkowski minkowski.o Triangulator.o UnionOfSpheres.o 
VisualizerGV.o  -lm -ldl -pg  '-L/opt/CGAL330/lib' -L/usr/lib/qt3 
-Wl,-R/opt/CGAL330/lib/i686_Linux-2.6_g++-4.1.2:/usr/lib/qt3 -lCGAL 
-lCGALcore++ -lCGALQt -lCGALimageIO -lCGALPDB -lqt-mt -lGL -lGLU -lz 
-lmpfr -lgmpxx -lgmp -lX11 -lboost_program_options -lm
==5523== Memcheck, a memory error detector.
==5523== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==5523== Using LibVEX rev 1658, a library for dynamic binary translation.
==5523== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==5523== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation 
framework.
==5523== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==5523== For more details, rerun with: -v
==5523==
Starting All...
Starting PowerDiagram Construction...
Reading input1
Number of spheres: 125
Reading input2
Number of spheres: 46
Triangulator: inserting 8 bounding spheres
lower=-2396.4, upper=2595.59
a
b
c
d
e
f
CGAL error: precondition violation!
Expr: orientation(p0, p1, p2, p3) == POSITIVE
File: /opt/CGAL330/include/CGAL/Regular_triangulation_3.h
Line: 890
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct NULL not valid
==5523==
==5523== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 97 from 1)
==5523== malloc/free: in use at exit: 1,165,510 bytes in 898 blocks.
==5523== malloc/free: 3,772 allocs, 2,874 frees, 1,309,384 bytes allocated.
==5523== For counts of detected errors, rerun with: -v
==5523== searching for pointers to 898 not-freed blocks.
==5523== checked 2,218,584 bytes.
==5523==
==5523== LEAK SUMMARY:
==5523==    definitely lost: 0 bytes in 0 blocks.
==5523==      possibly lost: 222 bytes in 7 blocks.
==5523==    still reachable: 1,165,288 bytes in 891 blocks.
==5523==         suppressed: 0 bytes in 0 blocks.
==5523== Reachable blocks (those to which a pointer was found) are not 
shown.
==5523== To see them, rerun with: --show-reachable=yes
Aborted (core dumped)
############################

..however, nothing happens if the assertions are disabled. You can try
it with my code: dist.ist.tugraz.at/test.tar.bz2

(includes and typedefs in common.h, the error occurs in
Triangulator.cpp)

g++ (GCC) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)

Options:
   -pg \
   -I../../include \
   $(CGAL_CXXFLAGS) \
   $(LONG_NAME_PROBLEM_CXXFLAGS) \
   -O3


Best
Bernhard