dD Triangulation crash with -O2 flag (ok in debug)

[etrinh]

With Mingw64 gcc 4.8.0, I have an assert when compiling this sample with -O2 or -O1 flag. Everything is ok in debug mode or when using Delaunay_triangulation.
I use:
CGAL 4.7
boost 1.59
eigen 3.2.7
gmp 6.1.0
mpfr 3.1.3

Result output:
Processing: 1/8
Processing: 2/8
Processing: 3/8
Processing: 4/8
Processing: 5/8
Processing: 6/8
Processing: 7/8
Assertion failed!

File: ............\Binaries\win64\include/Eigen/src/Core/DenseCoeffsBase.h, Line 337

Expression: row >= 0 && row < rows() && col >= 0 && col < cols()

And the call stack:

~"#0  0x00000000004124b0 in _wassert ()\n"
>~"#1  0x0000000000435c6e in operator() (col=2906769, row=7, this=0x22edd0) at ../../../../../../Binaries/win64/include/Eigen/src/Core/DenseCoeffsBase.h:336\n"
>~"#2  CGAL::CartesianDKernelFunctors::In_flat_orientation<CGAL::Cartesian_base_d<CGAL::Interval_nt<false>, CGAL::Dimension_tag<7>, CGAL::Default> >::operator()<CGAL::transforming_iterator<CGAL::KernelD_converter<CGAL::Cartesian_base_d<double, CGAL::Dimension_tag<7>, CGAL::Default>, CGAL::Cartesian_base_d<CGAL::Interval_nt<false>, CGAL::Dimension_tag<7>, CGAL::Default>, CGAL::typeset<CGAL::Sphere_tag, CGAL::typeset<CGAL::Hyperplane_tag, CGAL::typeset<CGAL::Segment_tag, CGAL::typeset<CGAL::Vector_tag, CGAL::typeset<CGAL::Point_tag, CGAL::typeset<void, void> > > > > > >, CGAL::transforming_iterator<CGAL::internal::Forward_rep, CGAL::Iterator_project<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false> const*, CGAL::internal::Triangulation::Point_from_vertex_handle<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dimension_tag<7> > > >, int, int, int, int>, CGAL::Default, CGAL::Default>, CGAL::Default, CGAL::Default> > (this=this@entry=0x22f9ed, o=..., f=..., e=...) at ../../../../../../Binaries/win64/include/CGAL/NewKernel_d/Coaffine.h:213\n"
>~"#3  0x0000000000432235 in operator()<CGAL::CartesianDKernelFunctors::Flat_orientation, CGAL::transforming_iterator<CGAL::internal::Forward_rep, CGAL::Iterator_project<const CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>*, CGAL::internal::Triangulation::Point_from_vertex_handle<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dimension_tag<7> > > >, int, int, int, int>, CGAL::Default, CGAL::Default>, CGAL::transforming_iterator<CGAL::internal::Forward_rep, CGAL::Iterator_project<const CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>*, CGAL::internal::Triangulation::Point_from_vertex_handle<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dimension_tag<7> > > >, int, int, int, int>, CGAL::Default, CGAL::Default> > (a2=..., a1=..., a0=..., this=0x22f9ec) at ../../../../../../Binaries/win64/include/CGAL/NewKernel_d/Filtered_predicate2.h:128\n"
>~"#4  operator()<CGAL::CartesianDKernelFunctors::Flat_orientation, CGAL::Iterator_project<const CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>*, CGAL::internal::Triangulation::Point_from_vertex_handle<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dimension_tag<7> > > >, int, int, int, int>, CGAL::Iterator_project<const CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>*, CGAL::internal::Triangulation::Point_from_vertex_handle<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dimension_tag<7> > > >, int, int, int, int> > (v=<synthetic pointer>, u1=<synthetic pointer>, u0=..., this=0x22f9ec) at ../../../../../../Binaries/win64/include/CGAL/NewKernel_d/Wrapper/Cartesian_wrap.h:160\n"
>~"#5  CGAL::Triangulation<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::Default>::Coaffine_orientation_d::operator()<CGAL::Iterator_project<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false> const*, CGAL::internal::Triangulation::Point_from_vertex_handle<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Triangulation_ds_vertex<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> > > >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dimension_tag<7> > > >, int, int, int, int> > (this=0x22f9e0, a=..., b=...) at ../../../../../../Binaries/win64/include/CGAL/Triangulation.h:107\n"
>~"#6  0x000000000043b8d2 in operator() (f=..., this=0x22fa10) at ../../../../../../Binaries/win64/include/CGAL/Triangulation.h:701\n"
>~"#7  CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> >::gather_full_cells<CGAL::Triangulation<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::Default>::Outside_convex_hull_traversal_predicate<CGAL::Triangulation<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::Default>::Coaffine_orientation_d>, std::back_insert_iterator<std::vector<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Triangulation_ds_full_cell<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> >, CGAL::Default> >, CGAL::Default, CGAL::Default, CGAL::Default>, false>, std::allocator<CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Triangulation_ds_full_cell<CGAL::Triangulation_data_structure<CGAL::Dimension_tag<7>, CGAL::Triangulation_vertex<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_vertex_data, CGAL::Default>, CGAL::Triangulation_full_cell<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::No_full_cell_data, CGAL::Default> >, CGAL::Default> >, CGAL::Default, CGAL::Default, CGAL::Default>, false> > > > > (this=this@entry=0x22fcd0, start=..., tp=..., out=...) at ../../../../../../Binaries/win64/include/CGAL/Triangulation_data_structure.h:710\n"
>~"#8  0x00000000004197fe in CGAL::Triangulation<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::Default>::insert_outside_convex_hull (this=0x22fcd0, p=..., s=...) at ../../../../../../Binaries/win64/include/CGAL/Triangulation.h:882\n"
>~"#9  0x0000000000419bd8 in CGAL::Triangulation<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::Default>::insert (this=this@entry=0x22fcd0, p=..., lt=<optimized out>, f=..., ft=..., s=...) at ../../../../../../Binaries/win64/include/CGAL/Triangulation.h:765\n"
>~"#10 0x0000000000419fc1 in CGAL::Triangulation<CGAL::Epick_d<CGAL::Dimension_tag<7> >, CGAL::Default>::insert (this=this@entry=0x22fcd0, p=..., start=...) at ../../../../../../Binaries/win64/include/CGAL/Triangulation.h:796\n"
>~"#11 0x00000000004456f1 in insert (v=..., p=..., this=0x22fcd0) at ../../../../../../Binaries/win64/include/CGAL/Triangulation.h:806\n"
>~"#12 main () at main.cpp:1982\n"

---

#include <CGAL/Epick_d.h>
#include <CGAL/Delaunay_triangulation.h>

int main()
{
   double pointsIn[][7] = {
    { 42.89, 0, 60.55, 30.72, 0, 0, 0 },
    { 45.65, 50.83, 50.37, 16.13, 0, 0, 0 },
    { 79.06, 57.84, 61.59, 2.52, 0, 0, 0 },
    { 44.47, 39.46, 39.53, 28.72, 0, 0, 0 },
    { 0, 100, 0, 0, 100, 0, 53.47 },
    { 66.95, 100, 33.6, 0, 0, 0, 0 },
    { 42.89, 0, 0, 30.72, 100, 0, 53.47 },
    { 100, 100, 100, 100, 100, 100, 100 }
    };

    typedef CGAL::Triangulation<CGAL::Epick_d< CGAL::Dimension_tag<7> > >      T;
    T dt(7);

    std::vector<T::Point> points;
    points.reserve(8);
    for (int j = 0; j < 8; ++j) {
        T::Point p(&pointsIn[j][0], &pointsIn[j][7]);
        points.push_back(p);
    }

    typename T::Vertex_handle hint;
    int i = 0;
    for(typename std::vector<T::Point>::iterator it = points.begin(); it != points.end(); ++it) {
        if (typename T::Vertex_handle() != hint) {
            hint = dt.insert(*it, hint);
        }
        else {
            hint = dt.insert(*it);
        }
        printf("Processing: %d/%d\n", ++i, (int)points.size());
    }
    return 0;
}

[afabri]

I can confirm that there is a problem. I get a segfault with VC12. We investigate.

[mglisse]

I am also getting the issue on linux, though it crashes a bit earlier (before printing 7/8).

[mglisse]

In Triangulation.h:

@@ -877,8 +877,9 @@
     std::back_insert_iterator<std::vector<Full_cell_handle> > out(simps);
     if( current_dimension() < maximal_dimension() )
     {
+        Coaffine_orientation_d ori = coaffine_orientation_predicate();
         Outside_convex_hull_traversal_predicate<Coaffine_orientation_d>
-            ochtp(*this, p, coaffine_orientation_predicate());
+            ochtp(*this, p, ori);
         tds().gather_full_cells(s, ochtp, out);
     }
     else

[afabri]

Thank you Mark. Do you take care of putting it in a git branch and integration, or shall GF do it?
The testsuite missed an execution branch. Can the package authors check if the testsuite can be improved.

[mglisse]

Sorry, not much time. I'll let you discuss that with @cjamin .

[etrinh]

I confirm the proposed patch fixes the issue at my side.
Thanks!