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