c++computational-geometrycgal

Behavioral difference between constructing a `Nef_polyhedron_3` directly from OFF file and constructing from a `Polyhedron_3` built from the same file

In CGAL, a Nef_polyhedron_3 can be built directly by loading an OFF file, or by building a Polyhedron_3 by loading the same OFF file and then constructing a Nef_polyhedron_3 from that.

A small example that does the former:

#include "common.hpp"

int main(int argc, char ** argv)
{
  Nef_polyhedron nef_poly;
  std::ifstream is("test.off", std::ios::in);
  CGAL::OFF_to_nef_3(is, nef_poly);
  is.close();

  return 0;
}

One that does the latter:

#include "common.hpp"

int main(int argc, char ** argv)
{
  Polyhedron poly;
  std::ifstream is("test.off", std::ios::in);
  bool success = CGAL::IO::read_OFF(is, poly);
  is.close();
  assert(success);
  assert(poly.is_valid());
  assert(poly.is_closed());

  Nef_polyhedron nef_poly(poly); // <--- A (see below).

  return 0;
}

Here common.hpp contains:

#pragma once
#include <iostream>
#include <fstream>
#include <cassert>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Polyhedron_OFF_iostream.h>
#include <CGAL/OFF_to_nef_3.h>

using Exact_kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Polyhedron = CGAL::Polyhedron_3<Exact_kernel>;
using Surface_mesh = CGAL::Surface_mesh<Exact_kernel::Point_3>;
using Nef_polyhedron = CGAL::Nef_polyhedron_3<Exact_kernel>;

From the documentation, I would expect the two to produce the same Nef polyhedron ("same" mathematically speaking). However, I can construct some OFF files for which only the former method works, while the latter fails with

terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: ss_circle.has_on(sp)
File: /usr/include/CGAL/Nef_3/polygon_mesh_to_nef_3.h
Line: 253

at the location labeled A.

Here's an OFF that exhibits that behavior:

OFF
5 5 10
-0.193282 0.100467 0.339231
-0.183855 0.102082 0.334972
-0.183473 0.103303 0.332011
-0.181318 0.104688 0.348585
0.000000 0.000000 0.000000
3 4 0 1
3 4 1 2
3 4 2 3
3 4 3 0
4 3 2 1 0

Here's one where the two approaches produce the same polyhedron, as I would expect in general:

OFF
8 6 12
 1.0  0.0 1
 0.0  1.0 1
-1.0  0.0 1
 0.0 -1.0 1
 1.0  0.0 0.0
 0.0  1.0 0.0
-1.0  0.0 0.0
 0.0 -1.0 0.0
4 0 1 2 3
4 7 4 0 3
4 4 5 1 0
4 5 6 2 1
4 3 2 6 7

I assume I've misunderstood something in the CGAL documentation for these classes. Is it obvious exactly what that is?

As an addendum, here's a simple visualization of the edges of the OFF that breaks. Nothing too spooky going on there. The orange edges are the ones that make up the boundary of the only non-triangle surface segment. Illustration of breaking OFF

Solution

  • The first OFF file you provided contains a non-planar facet (4 3 2 1 0), which can't be processed by the Nef_polyhedron_3 constructor. However such facets can be handled by more advanced function CGAL::OFF_to_nef_3(...), which is explicitly stated in its header:

    This function creates a 3D Nef polyhedron from an OFF file which is read from input stream in. The purpose of OFF_to_nef_3 is to create a Nef polyhedron from an OFF file that cannot be handled by the Nef_polyhedron_3 constructors. It handles double coordinates while using a homogeneous kernel, non-coplanar facets, surfaces with boundaries, self-intersecting surfaces, and single facets. Every closed volume gets marked. The function returns the number of facets it could not handle.

    So, if you split this non-planar facet into two triangles then both OFF-handling functions will be able to process the modified OFF file:

     OFF
5 6 0
-0.193282 0.100467 0.339231
-0.183855 0.102082 0.334972
-0.183473 0.103303 0.332011
-0.181318 0.104688 0.348585
0.000000 0.000000 0.000000
3 4 0 1
3 4 1 2
3 4 2 3
3 4 3 0
3 3 1 0
3 3 2 1

    ADDITION. The Nef polyhedron, created from the first OFF file with the aid of the CGAL::OFF_to_nef_3 function, can be visualized with the function CGAL:draw(...):

    The first OFF file visualization

    You can see, that the non-planar facet was automatically triangulated by addition of one extra-edge, and it looks like it was done correctly.