mesh simplifcation/edge collapse using the lindstrom-turk strategy results in weird, ultra-distant vertices

[ruben-benaco]

I have a mesh (link to input.ply on github), with 1'669'389 faces. I use the code below to simplify down to 350'000 faces.

The result is shown in the screenshot below: at least two vertices appeared far away from the mesh. I selected one of the corresponding edges in Blender, showing in white.

The problem only appears

• when using the lindstrom-turk cost/placement strategy - i didn't observe the problem with any of the garland-heckbert strategies
• when simplifying to low face counts, I can simplify to 1'000'000 faces without issue

#include <CGAL/Surface_mesh.h>
#include <CGAL/Surface_mesh_simplification/edge_collapse.h>
#include <CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Bounded_normal_change_filter.h>
#include <CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Face_count_stop_predicate.h>
#include <CGAL/Surface_mesh_simplification/Policies/Edge_collapse/LindstromTurk_cost.h>
#include <CGAL/Surface_mesh_simplification/Policies/Edge_collapse/LindstromTurk_placement.h>
#include <CGAL/Surface_mesh/IO/PLY.h>
#include <CGAL/IO/polygon_soup_io.h>
#include <CGAL/Polygon_mesh_processing/orient_polygon_soup_extension.h>
#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>
#include <cstdlib>
#include <iostream>
#include <fstream>

namespace SMS = CGAL::Surface_mesh_simplification;

typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3> Surface_mesh;

int main(int argc, char** argv) {

  std::string filename("input.ply");
  const size_t target_number_of_faces = 350000;

  std::vector<Kernel::Point_3> vertices;
  std::vector<std::array<size_t, 3>> faces;

  if (!CGAL::IO::read_polygon_soup(filename, vertices, faces)) {
    std::cerr << "Failed to read input mesh from file." << std::endl;
    return EXIT_FAILURE;
  }

  Surface_mesh surface_mesh;

  CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup(vertices, faces);
  CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh(vertices, faces, surface_mesh);

  if(!CGAL::is_triangle_mesh(surface_mesh)) {
    std::cerr << "Input geometry is not triangulated." << std::endl;
    return EXIT_FAILURE;
  }

  SMS::Face_count_stop_predicate<Surface_mesh> stop(target_number_of_faces);

  std::cout << "Input mesh number of faces: " << surface_mesh.number_of_faces() << ", target number of faces: " << target_number_of_faces << std::endl;

  SMS::edge_collapse(
    surface_mesh,
    stop,
    CGAL::parameters::
       filter(SMS::Bounded_normal_change_filter<>())
      .get_cost(SMS::LindstromTurk_cost<Surface_mesh>())
      .get_placement(SMS::LindstromTurk_placement<Surface_mesh>())
    );
  std::string out_file = "output.ply";
  std::ofstream stream(out_file, std::ios::binary);
  CGAL::set_binary_mode(stream);
  CGAL::IO::write_PLY(stream, surface_mesh, CGAL::parameters::stream_precision(17));
  return EXIT_SUCCESS;
}

Environment

• Linux, NixOS 64 bits
• compiler: g++
• CGAL version: 5.5.2, with Face_count_stop_predicate.h from latest

[afabri]

We can investigate, but are you sure surface mesh simplification is the right thing for the mesh you have at hand? How do you obtain this heavily self intersecting mesh, and what do you want to do with it downstream?

[ruben-benaco]

We can investigate, but are you sure surface mesh simplification is the right thing for the mesh you have at hand? How do you obtain this heavily self intersecting mesh, and what do you want to do with it downstream?

I put this specific mesh there for easy reproducibility of the issue. We use mesh simplification as part of an automated toolchain. The input meshes vary in size, shape and topology. I was looking for a mesh simplification algorithm that can produce somewhat consistent results when I encountered the issue.

Further examples of the same issue (always lindstrom-turk at low face counts):

[afabri]

Hu @ruben-benaco, in the above mentioned pull request we added a rather add-hoc robustification. In case the placement is outside a slightly enlarged bounding box of the link ( the vertices incident to the vertices on the edge to collapse) we drop it. We have to think about a better solution, but it might help you for now.

And I would be glad to discuss with you about your pipeline. If I had to deal with meshes as the one you shared with us, I first would remove all connected components which are small, Here is a link to such a function.