CGAL users discussion list

[Gard Spreemann <>]

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

Attachment: signature.asc
Description: PGP signature