CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Hello,

The patch in https://github.com/CGAL/cgal/pull/8646 should fix your issue.

Best,

Sebastien

On 1/11/25 10:57, Gard Spreemann wrote:
> Hello,
>
> I'm seeing some assertion violations regarding certain halfspace
> intersections computed using Nef polyhedra.
>
> As a simple example, consider the following example program:
>
> ***
> #include <iostream>
>
> #include <CGAL/Extended_cartesian.h>
> #include <CGAL/Gmpq.h>
> #include <CGAL/Nef_polyhedron_3.h>
>
> using Kernel = CGAL::Extended_cartesian<CGAL::Gmpq>;
> using Nef = CGAL::Nef_polyhedron_3<Kernel>;
>
> int main(int argc, char ** argv)
> {
>    Nef hspace_1_1(Nef::Plane_3(1.0, 0.0, 0.0, 0.0), Nef::INCLUDED);
>    Nef hspace_1_2(Nef::Plane_3(1.0, 0.0, 0.0, 1.0), Nef::INCLUDED);
>    Nef hspace_2_1(Nef::Plane_3(0.0, 1.0, 0.0, 0.0), Nef::INCLUDED);
>    Nef hspace_2_2(Nef::Plane_3(0.0, 1.0, 0.0, 1.0), Nef::INCLUDED);
>    Nef hspace_3_1(Nef::Plane_3(0.0, 0.0, 1.0, 0.0), Nef::INCLUDED);
>    Nef hspace_3_2(Nef::Plane_3(0.0, 0.0, 1.0, 1.0), Nef::INCLUDED);
>
>    Nef intersection_1 = hspace_1_1*hspace_1_2;
>    std::cout << "OK 1" << std::endl;
>    
>    Nef intersection_2 = hspace_2_1*hspace_2_2;
>    std::cout << "OK 2" << std::endl;
>      
>    Nef intersection_3 = hspace_3_1*hspace_3_2;
>    std::cout << "OK 3" << std::endl;
>
>    Nef intersection_1_2 = intersection_1*intersection_2;
>    std::cout << "OK 1_2" << std::endl;
>    Nef intersection_1_3 = intersection_1*intersection_3; // Line 30
>    std::cout << "OK 1_3" << std::endl;
>    Nef intersection_2_3 = intersection_2*intersection_3;
>    std::cout << "OK 2_3" << std::endl;
>    
>    return 0;
> }
> ***
>
> To me, there doesn't seem to be anything mathematically conceptually
> different about the intersections that define `intersection_1_2` and
> those which define `intersection_1_3`. Yet, the latter computation
> terminates with an assertion violation. Here's the gdb backtrace:
>
> #5  0x00007ffff7ca8e85 in std::terminate() () from 
> /lib/x86_64-linux-gnu/libstdc++.so.6
> #6  0x00007ffff7ca90d8 in __cxa_throw () from 
> /lib/x86_64-linux-gnu/libstdc++.so.6
> #7  0x000055555555dc5e in CGAL::assertion_fail (
>      expr=0x55555562c7c8 "normalized(cet->circle()) == 
> normalized(ce->circle().opposite())",
>      file=0x55555562c738 "/usr/include/CGAL/Nef_3/SNC_external_structure.h", line=697, 
> msg=0x55555562b09c "")
>      at /usr/include/CGAL/assertions_impl.h:173
> #8  0x000055555556d9a5 in CGAL::SNC_external_structure_base<CGAL::SNC_items, 
> CGAL::SNC_structure<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, bool> 
> >::link_shalfedges_to_facet_cycles (this=0x7fffffffda60)
>      at /usr/include/CGAL/Nef_3/SNC_external_structure.h:697
> #9  0x0000555555566724 in CGAL::SNC_external_structure_base<CGAL::SNC_items, 
> CGAL::SNC_structure<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, bool> 
> >::build_external_structure (this=0x7fffffffda60)
>      at /usr/include/CGAL/Nef_3/SNC_external_structure.h:1014
> #10 0x0000555555572684 in CGAL::SNC_external_structure_base<CGAL::SNC_items, 
> CGAL::SNC_structure<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, bool> 
> >::build_after_binary_operation<CGAL::ID_support_handler<CGAL::SNC_items, 
> CGAL::SNC_decorator<CGAL::SNC_structure<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, bool> > > 
> > (this=0x7fffffffda60)
>      at /usr/include/CGAL/Nef_3/SNC_external_structure.h:1049
> #11 0x0000555555567c58 in 
> CGAL::Binary_operation<CGAL::SNC_structure<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, 
> bool> >::operator()<CGAL::Nef_polyhedron_3<CGAL::Extended_cartesian<CGAL::Gmpq>, 
> CGAL::SNC_items, bool>::AND> (this=0x7fffffffdc40,
>      pl0=0x5555557d5790, snc1=..., pl1=0x5555557a8b80, snc2=..., 
> pl2=0x5555557c9630, BOP=...)
>      at /usr/include/CGAL/Nef_3/Binary_operation.h:525
> #12 0x00005555555637e5 in 
> CGAL::Nef_polyhedron_3<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, 
> bool>::intersection (
>      this=0x7fffffffdd30, N1=...) at /usr/include/CGAL/Nef_polyhedron_3.h:1416
> #13 0x0000555555562313 in 
> CGAL::Nef_polyhedron_3<CGAL::Extended_cartesian<CGAL::Gmpq>, CGAL::SNC_items, 
> bool>::operator* (
>      this=0x7fffffffdd30, N1=...) at /usr/include/CGAL/Nef_polyhedron_3.h:1488
> #14 0x000055555555b298 in main (argc=1, argv=0x7fffffffe048) at test.cpp:30
>
> If I flip the signs of the `d` arguments in all the halfspace
> constructions, i.e. make them `Nef hspace_1_2(Nef::Plane_3(1.0, 0.0,
> 0.0, -1.0), Nef::INCLUDED)` etc., then the whole program terminates
> normally. Seeing as that sign only shifts some of the halfspaces in a
> direction normal to their defining planes, I'm very surprised that this
> has an effect.
>
> Does anyone see anything obvious that I'm overlooking or
> misunderstanding here?
>
>
>   Best,
>   Gard