CGAL users discussion list

[as84 <>]

Hello,

I'm new to CGAL and have run into the following problems. I need to do
boolean operations on polyhedra and it seems like CGAL's Nef polyhedra are
the way to go. Unfortunately, when trying to convert my input polyhedra to
Nef polyhedra I get assertions in "polyhedron_3_to_nef_3". Trying to
directly build Nef polyhedra out of intersections of half-spaces instead
seems prohibitively costly (see further down).

The following program causes an assertion for the given polyhedron:


#include <iostream>

#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
//typedef CGAL::Extended_cartesian<CGAL::Gmpq>  Kernel;

typedef CGAL::Polyhedron_3<Kernel>  Polyhedron;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;

using namespace std;


// polyhedron in OFF format representation
const char* polyhedronOffStr =
"OFF \n"
"8 6 0 \n"
" \n"
"-0.169499993324289777 0.242500001788149344 0.0144999995827574911 \n"
"-0.169499993324289805 0.242500001788149372 0.0153333330527079537 \n"
"-0.166500002145693882 0.242500001788149344 0.0144999995827574911 \n"
"-0.169499993324289777 0.22350001335141631 0.0144999995827574876 \n"
"-0.169499993324289777 0.22350001335141631 0.0153333330527079537 \n"
"-0.166500002145693882 0.226500004530012206 0.0144999995827574876 \n"
"-0.169499993324289777 0.223500013351416282 0.0149085206319855799 \n"
"-0.168029322112646429 0.224970684563059659 0.0144999995827574876 \n"
"3  1 2 0 \n"
"5  3 6 4 1 0 \n"
"5  0 2 5 7 3 \n"
"4  1 4 5 2 \n"
"4  6 7 5 4 \n"
"3  3 7 6 \n";

// same polyhedron with triangulated facets
const char* polyhedronOffStrTriangulated =
"OFF \n"
"8 12 0 \n"
" \n"
"-0.169499993324289777 0.242500001788149344 0.0144999995827574911 \n"
"-0.169499993324289805 0.242500001788149372 0.0153333330527079537 \n"
"-0.166500002145693882 0.242500001788149344 0.0144999995827574911 \n"
"-0.169499993324289777 0.22350001335141631 0.0144999995827574876 \n"
"-0.169499993324289777 0.22350001335141631 0.0153333330527079537 \n"
"-0.166500002145693882 0.226500004530012206 0.0144999995827574876 \n"
"-0.169499993324289777 0.223500013351416282 0.0149085206319855799 \n"
"-0.168029322112646429 0.224970684563059659 0.0144999995827574876 \n"
"3  0 1 2 \n"
"3  0 3 6 \n"
"3  0 6 4 \n"
"3  0 4 1 \n"
"3  3 0 2 \n"
"3  3 2 5 \n"
"3  3 5 7 \n"
"3  2 1 4 \n"
"3  2 4 5 \n"
"3  4 6 7 \n"
"3  4 7 5 \n"
"3  6 3 7 \n";

int main()
{
    // create polyhedron
    Polyhedron P;
    istringstream off(polyhedronOffStr);
    // uncomment this line instead of the one above to get a different
assertion
    // istringstream off(polyhedronOffStrTriangulated);
    off >> P;
    std::cout << "Polygon is_valid: " << P.is_valid()
              << ", is_closed: " << P.is_closed() << std::endl  <<
std::endl;
    // convert to nef polyhedron
    Nef_polyhedron NP(P);

    return 0;
}


The output of the program is:

> Polygon is_valid: 1, is_closed: 1
>
> terminate called after throwing an instance of 'CGAL::Assertion_exception'
>   what():  CGAL ERROR: assertion violation!
> Expr: pe_prev->is_border() ||
> internal::Plane_constructor<Plane>::get_plane(pe_prev->facet(),pe_prev->facet()->plane())
> has_on(pe_prev->opposite()->vertex()->point())
> File: /home/user/CGAL-4.2/include/CGAL/Nef_3/polyhedron_3_to_nef_3.h
> Line: 254

I suspected this might be because the facets of the polygon are not
perfectly planar. They should be by construction, but some of the vertex
coordinates which should be equal differ in the last bit of the mantissa due
to rounding error. As an attempt to work around this I triangulated the
polygon's facets, which can be tested by replacing "polyhedronOffStr" on
line 67 with "polyhedronOffStrTriangulated".
This, however, causes a different assertion (and a not quite helpful error
message immediately before it):

> Polygon is_valid: 1, is_closed: 1
>
> Error !!!!!!!!!!!!!!!!!!!!!!!
> terminate called after throwing an instance of 'CGAL::Assertion_exception'
>   what():  CGAL ERROR: assertion violation!
> Expr: pe_prev->is_border() ||
> !internal::Plane_constructor<Plane>::get_plane(pe_prev->facet(),pe_prev->facet()->plane()).is_degenerate()
> File: /home/user/CGAL-4.2/include/CGAL/Nef_3/polyhedron_3_to_nef_3.h
> Line: 251


Another thought I had: As my input polygons are convex (before applying the
boolean operations I need CGAL for), I should be able to construct them as
an intersection of half-spaces. This isn't possible with the
Exact_predicates_exact_constructions_kernel Kernel unfortunately. I'm not
sure which is the best choice for an extended kernel as I need vertex
coordinates converted from double. I've tried with the following kernel but
it is _VERY_ slow:
typedef CGAL::Extended_cartesian<CGAL::Gmpq>  Kernel;

I ran a simple speed test. Clipping a cube with a plane using 1) my own code
for polyhedra using plain double values, 2) CGAL's nef code with
Exact_predicates_exact_constructions_kernel, and 3) the
CGAL::Extended_cartesian<CGAL::Gmpq> kernel
It took (averaged over many runs, release build)
1) 0.015 ms
2) 3.3 ms
3) 510 ms


Any help on this is much appreciated.

Best regards,
Andre



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/Assertion-converting-Polyhedron-3-to-Nef-polyhedron-3-Nef-polyhedron-VERY-slow-with-extended-kernel-tp4658058.html
Sent from the cgal-discuss mailing list archive at Nabble.com.