Openscad produces is_ccw_strongly_convex_2 assertion

[More-Wrong]

Fails when running Openscad 2015.03-1 under ubuntu 15.10
Cpu: Intel® Core™ i5-2500 CPU @ 3.30GHz × 4

is_ccw_strongly_convex_2( res.output_so_far_begin(), res.output_so_far_end(), ch_traits)

When opening Openscad on a file containing the code below, Openscad will crash instantly, or if the code is pasted in, will crash on the first preview or render (f5 or f6).

Sample failing code:

  w = 10;
  t = 2;
  $fn = 20;
  hull(){
     translate([0,3*w/4]){
        rotate([0,0,60]){
           translate([-10, -w/2+0.05]){
              square([10, t]);
           }
        }
     }
     translate([-w/2, -w/2+t]){
        square([t, 0.000000000000001]);
     }
  }

Error details:

CGAL error: postcondition violation!
Expression : is_ccw_strongly_convex_2( res.output_so_far_begin(), res.output_so_far_end(), ch_traits)
File : /usr/include/CGAL/Convex_hull_2/ch_akl_toussaint_impl.h
Line : 337
Explanation:
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html
Aborted (core dumped)

[sloriot]

I think you should first report this error to Openscad team as we have no clue how the CGAL code is used in there.

[kintel]

This looks like a CGAL bug. I'll try to toss together a minimal example later, but here's the gist of it:

typedef CGAL::Point_2<CGAL::Cartesian<double>> CGALPoint2;
std::list<CGALPoint2> points;
std::list<CGALPoint2> result;
CGAL::convex_hull_2(points.begin(), points.end(), std::back_inserter(result));

..where points are these 2D vertices:

-0.713174 -3.63525
4.28683 5.025
2.55477 6.025
-2.44523 -2.63525
-5 -3
-3 -3
-3 -3
-5 -3

...which this stack trace:

#3	0x0000000101d57d70 in CGAL::postcondition_fail(char const*, char const*, int, char const*) ()
#4	0x00000001002c31d0 in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > > CGAL::ch_akl_toussaint<std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > >, CGAL::Cartesian<double> >(std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > >, CGAL::Cartesian<double> const&) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Convex_hull_2/ch_akl_toussaint_impl.h:334
#5	0x00000001002bf6b5 in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > > CGAL::CGAL_convex_hull_points_2<std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > >, CGAL::Cartesian<double> >(std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > >, CGAL::Cartesian<double> const&, std::__1::bidirectional_iterator_tag) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/convex_hull_2.h:57
#6	0x00000001002bf661 in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > > CGAL::convex_hull_points_2<std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > > >(std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > >) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/convex_hull_2.h:94
#7	0x00000001002b49cd in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > > CGAL::convex_hull_2<std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > > >(std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::__list_iterator<CGAL::Point_2<CGAL::Cartesian<double> >, void*>, std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, std::__1::allocator<CGAL::Point_2<CGAL::Cartesian<double> > > > >) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/convex_hull_2.h:124
#8	0x00000001002a1f1c in GeometryEvaluator::applyHull2D(AbstractNode const&) at /Users/kintel/code/OpenSCAD/openscad/src/GeometryEvaluator.cc:166

[kintel]

Here's a reproducible minimal test case:
I've made minimal changes to examples/Convex_hull_2/iostream_convex_hull_2.cpp.

Run like this: ./iostream_convex_hull_2 < input.txt

NB! To reproduce you need to compile the example without the -DNDEBUG flag.

Source:

#include <iostream>
#include <iterator>
#include <CGAL/Cartesian.h>
#include <CGAL/convex_hull_2.h>
typedef CGAL::Point_2<CGAL::Cartesian<double>> Point_2;
int main()
{
  std::istream_iterator< Point_2 >  input_begin( std::cin );
  std::istream_iterator< Point_2 >  input_end;
  std::ostream_iterator< Point_2 >  output( std::cout, "\n" );
  CGAL::convex_hull_2( input_begin, input_end, output );
  return 0;
}

input.txt:

-0.713174251267 -3.6352540378443869
4.2868257487329 5.024999999999999
2.5547749411640 6.024999999999999
-2.445225058835 -2.63525403784438516
-5 -3
-3 -3
-3 -2.999999999999999
-5 -2.999999999999999

PS! We need to build without -NDEBUG in production to be able to catch certain CGAL errors, in order to provide a more robust code path or provide error messages in the event that CGAL fails.

[sloriot]

You should read this FAQ entry.

Replacing the kernel type with CGAL::Exact_predicates_inexact_constructions_kernel fixed the error.

[kintel]

Thanks for the clarification. I hadn't expected convex_hull_2 to require an exact kernel, but good to know.

It actually looks like convex_hull_2 itself is stable with a cartesian kernel, but the postcondition check is not.