Alpha Wrapping Strange Features

altonlm commented 1 year ago

Issue Details

I've apha-wrapped ~400 stl format meshes using a slightly modified version of the alpha wrapping example script and, on four out of the 400, strange triangles appeared connecting different components. I have a link to the original meshes in question and various alpha wrapping attempts. The meshes are all named according to this format: .off

The ones originally noticed with this issue have a relativeAlpha of 1000 and a relativeOffset of 4000 however (on the same mesh) offsets similar to 4000 can also exhibit the same behavior.

This isn't pressing as I can just use the ones with a relativeOffset of 4050 however I would like to understand the issue, if possible, and make sure that this is known about if it is unintended.

Source Code

This is the source code that I used which is a minimally changed version of the alphawrapping demo code triangle_mesh_wrap.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/alpha_wrap_3.h>
#include <CGAL/Polygon_mesh_processing/bbox.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Real_timer.h>

#include <iostream>
#include <string>

namespace AW3 = CGAL::Alpha_wraps_3;
namespace PMP = CGAL::Polygon_mesh_processing;

using K = CGAL::Exact_predicates_inexact_constructions_kernel;
using Point_3 = K::Point_3;
using Mesh = CGAL::Surface_mesh<Point_3>;

int main(int argc, char** argv)
{
  std::cout.precision(17);
  // Read the input
  const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/armadillo.off");
  std::cout << "Reading " << filename << "..." << std::endl;
  Mesh mesh;
  if(!PMP::IO::read_polygon_mesh(filename, mesh) || is_empty(mesh) || !is_triangle_mesh(mesh))
  {
    std::cerr << "Invalid input." << std::endl;
    return EXIT_FAILURE;
  }
  std::cout << "Input: " << num_vertices(mesh) << " vertices, " << num_faces(mesh) << " faces" << std::endl;
  // Compute the alpha and offset values
  const double relative_alpha = (argc > 2) ? std::stod(argv[2]) : 20.;
  const double relative_offset = (argc > 3) ? std::stod(argv[3]) : 600.;
  CGAL::Bbox_3 bbox = CGAL::Polygon_mesh_processing::bbox(mesh);
  const double diag_length = std::sqrt(CGAL::square(bbox.xmax() - bbox.xmin()) +
                                       CGAL::square(bbox.ymax() - bbox.ymin()) +
                                       CGAL::square(bbox.zmax() - bbox.zmin()));
  const double alpha = diag_length / relative_alpha;
  const double offset = diag_length / relative_offset;
  // Construct the wrap
  CGAL::Real_timer t;
  t.start();
  Mesh wrap;
  CGAL::alpha_wrap_3(mesh, alpha, offset, wrap);
  t.stop();
  std::cout << "Result: " << num_vertices(wrap) << " vertices, " << num_faces(wrap) << " faces" << std::endl;
  std::cout << "Took " << t.time() << " s." << std::endl;
  // Save the result
  std::string input_name = std::string(filename);
  input_name = input_name.substr(input_name.find_last_of("/") + 1, input_name.length() - 1);
  input_name = input_name.substr(0, input_name.find_last_of("."));
  std::string output_name = input_name
                            + "_" + std::to_string(static_cast<int>(relative_alpha))
                            + "_" + std::to_string(static_cast<int>(relative_offset)) + ".off";
  std::cout << "Writing to " << output_name << std::endl;
  CGAL::IO::write_polygon_mesh(output_name, wrap, CGAL::parameters::stream_precision(17));
  return EXIT_SUCCESS;
}

Environment

Operating system (Windows/Mac/Linux, 32/64 bits): MacOS with M2
Compiler: g++
Release or debug mode: Release
Specific flags used (if any): -DCMAKE_BUILD_TYPE=Release
CGAL version: 5.5.2
Boost version: 1.82.0_1
Other libraries versions if used (Eigen, TBB, etc.): None that I know of

afabri commented 1 year ago

Which are the four files ?

MaelRL commented 1 year ago

There are only four files + results in the OP's zip.

I'm looking into it. I'd guess it's the optional manifoldness criterion, which flags incident outside tetrahedra as "inside" to recover manifoldness of the output.

MaelRL commented 1 year ago

It was indeed coming from the (optional) manifoldness post-processing. This step is improved with https://github.com/CGAL/cgal/pull/7629, see the pull request for details.

@altonlm I checked the result for all your examples and all alpha / delta values, and it was all fine. Could we please add this data into our tests (meaning, adding the data into the public data dir of CGAL: https://github.com/CGAL/cgal/tree/master/Data/data/meshes)?

altonlm commented 1 year ago

I believe that that should be fine. The original data isn't mine and is from this dataset: https://www.microns-explorer.org/phase1 but I don't think there should be any issues with you using it as test cases. Thank you for the help!

MaelRL commented 10 months ago

Fixed with the merge of #7805.

Thanks @altonlm for the bug report.

CGAL / cgal