autorefine_triangle_soup sometimes resolves self-intersection by producing non-manifold structure

[pentacular]

Issue Details

I am trying to resolve self-intersections which are self-touches -- i.e., no interpenetration.

autorefine_triangle_soup looks like it should do this, but I find that it prefers to resolve self-intersection by producing non-manifold results. :)

Below I include a test-case which builds two tetrahedrons with one common point, but no common vertices.

Is there a way to get it to either cleanly separate or cleanly merge the volumes?

Thanks.

Source Code

#include <cassert>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>
#include <utility>
#include <vector>

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/IO/OBJ.h>
#include <CGAL/Polygon_mesh_processing/autorefinement.h>
#include <CGAL/Polygon_mesh_processing/manifoldness.h>
#include <CGAL/Polygon_mesh_processing/self_intersections.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/measure.h>
#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>
#include <CGAL/Surface_mesh.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Epeck;
typedef Epeck::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Surface_mesh;

void test_self_point_touch_repair() {
  std::vector<Point_3> original_soup_points;
  std::vector<std::array<std::size_t, 3>> original_soup_triangles;

  // Tetrahedron 1 points
  original_soup_points.push_back(Point_3(0, 0, 0));
  original_soup_points.push_back(Point_3(1, 0, 0));
  original_soup_points.push_back(Point_3(0, 1, 0));
  original_soup_points.push_back(Point_3(0, 0, 1));

  // Tetrahedron 2 points
  original_soup_points.push_back(Point_3(0, 0, 0));
  original_soup_points.push_back(Point_3(-1, 0, 0));
  original_soup_points.push_back(Point_3(0, -1, 0));
  original_soup_points.push_back(Point_3(0, 0, -1));

  // Faces for Tetrahedron 1 (using indices 0,1,2,3)
  original_soup_triangles.push_back({0, 1, 2});
  original_soup_triangles.push_back({0, 2, 3});
  original_soup_triangles.push_back({0, 3, 1});
  original_soup_triangles.push_back({1, 3, 2});

  // Faces for Tetrahedron 2 (using indices 4,5,6,7)
  original_soup_triangles.push_back({4, 5, 6});
  original_soup_triangles.push_back({4, 6, 7});
  original_soup_triangles.push_back({4, 7, 5});
  original_soup_triangles.push_back({5, 7, 6});

  // Write original soup to OBJ
  std::ofstream original_outfile("original.obj");
  CGAL::IO::write_OBJ(original_outfile, original_soup_points, original_soup_triangles);
  original_outfile.close();

  // The original is a manifold self-intersecting at (0, 0, 0).
  /*
    v 0 0 0
    v 1 0 0
    v 0 1 0
    v 0 0 1
    v 0 0 0
    v -1 0 0
    v 0 -1 0
    v 0 0 -1
    f  1 2 3
    f  1 3 4
    f  1 4 2
    f  2 4 3
    f  5 6 7
    f  5 7 8
    f  5 8 6
    f  6 8 7
  */

  std::vector<Point_3> repaired_soup_points = original_soup_points;
  std::vector<std::array<std::size_t, 3>> repaired_soup_triangles = original_soup_triangles;

  const auto& snap_rounding_option =
      CGAL::parameters::apply_iterative_snap_rounding(true);
  bool success_autorefine =
      CGAL::Polygon_mesh_processing::autorefine_triangle_soup(
          repaired_soup_points, repaired_soup_triangles, snap_rounding_option);
  assert(success_autorefine);

  // Write repaired soup to OBJ
  std::ofstream outfile_soup("result_soup.obj");
  CGAL::IO::write_OBJ(outfile_soup, repaired_soup_points,
                      repaired_soup_triangles);
  outfile_soup.close();

  // autorefine_triangle_soup merges the two (0, 0, 0) resolving the self-intersection
  // but making it non-manifold.
  /*
    v 0 0 0
    v 1 0 0
    v 0 1 0
    v 0 0 1
    v -1 0 0
    v 0 -1 0
    v 0 0 -1
    f  1 2 3
    f  1 3 4
    f  1 4 2
    f  2 4 3
    f  1 5 6
    f  1 6 7
    f  1 7 5
    f  5 7 6
  */

  // Separating the points via snap-rounding would solve the problem correctly,
  // but this solution seems inaccessible.
}

int main() {
  test_self_point_touch_repair();
  return 0;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Linux 64 bit
• Compiler: gcc
• Release or debug mode:
• Specific flags used (if any):
• CGAL version: head
• Boost version:
• Other libraries versions if used (Eigen, TBB, etc.):

[sloriot]

Note that the only goal of autorefine is to resolve the self-intersections of triangles.
It is not meant to fix incorrect orientation of your mesh, nor to resolve non-manifold situation in your input. Moreover, if you have a self-intersection of triangles, intersecting in their interior for sure you will obtain some non-manifold edges in the output.
We started to implement the post-processing functions to be used after autorefine for doing repair but they are not yet ready to be released

[pentacular]

The input is manifold -- it's just self-touching.

autorefine_triangle_soup is producing the non-manifold structure as a way to remove the self-intersection.

The result is that the geometry produced is invalid, and if you fix the manifold, it will once again be self-intersecting.

The only way to fix this problem is to move the points apart.

Unfortunately having covered up the problem, it is now unable to move the points apart via snap rounding.

So I don't think post-processing is going to help here -- there needs to be some way to inhibit the generation of this non-manifold structure.