[Shortest Paths] There are situations where there is no return point set and a large number of duplicate points occur

Question

[Shortest Paths] There are situations where there is no return point set and a large number of duplicate points occur

Opened this issue 4 months ago · 5 comments

Hello, I encountered a series of problems when testing the function of Triangulated Surface Mesh Shortest Paths to find the shortest path of any two points on the model surface using other models. For example, when using the bathtub model, the path point returned by the algorithm was 0. When testing with the hilbert_cube2_pds_100k_surface.obj model provided by your KSR, a large number of duplicate points occurred, and some points drifted off the surface of the model. The following are my running environment, code and model file

Runtime environment

Operating system:Windows 11
Compiler:Visual Studio2022
CGAL version:6.0.1
Boost version:1.88.0

Code

The code when using the bathtub model

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>

#include <CGAL/Surface_mesh_shortest_path.h>
#include <CGAL/Random.h>

#include <boost/lexical_cast.hpp>

#include <cstdlib>
#include <iostream>
#include <fstream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3> Triangle_mesh;
typedef CGAL::Surface_mesh_shortest_path_traits<Kernel, Triangle_mesh> Traits;
typedef CGAL::Surface_mesh_shortest_path<Traits> Surface_mesh_shortest_path;
typedef boost::graph_traits<Triangle_mesh> Graph_traits;
typedef Graph_traits::vertex_iterator vertex_iterator;
typedef Graph_traits::face_iterator face_iterator;

int main(int argc, char** argv)
{
    const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("bathtub_0001.obj");

    Triangle_mesh tmesh;
    if (!CGAL::IO::read_polygon_mesh(filename, tmesh))
    {
        std::cerr << "Invalid input file1." << std::endl;
        return EXIT_FAILURE;
    }

    const int target_face_index = 79;
    face_iterator face_it = faces(tmesh).first;
    std::advance(face_it, target_face_index);
    // ... and define a barycentric coordinates inside the face
    Traits::Barycentric_coordinates face_location1 = { {0.04761892557144165,0.5907313227653503,0.36164984107017517} };
    Traits::Barycentric_coordinates face_location2 = { {0.3858107328414917, 0.3522464334964752,0.2619428336620331} };

    // construct a shortest path query object and add a source point
    Surface_mesh_shortest_path shortest_paths(tmesh);
    shortest_paths.add_source_point(*face_it, face_location1);
    std::cout << *face_it << std::endl;
    // For all vertices in the tmesh, compute the points of
    // the shortest path to the source point and write them
    // into a file readable using CGAL Lab
    std::ofstream output("shortest_paths.txt");
    face_iterator f_it = faces(tmesh).first;
    std::advance(f_it, 750);
    std::vector<Traits::Point_3> points;
    std::cout << *f_it << std::endl;
    shortest_paths.shortest_path_points_to_source_points(*f_it, face_location2, std::back_inserter(points));

    // print the points
    output << points.size() << " ";
    for (std::size_t i = 0; i < points.size(); ++i)
        output << " " << points[i];
    output << std::endl;
}

The code when using the cube model

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>

#include <CGAL/Surface_mesh_shortest_path.h>
#include <CGAL/Random.h>

#include <boost/lexical_cast.hpp>

#include <cstdlib>
#include <iostream>
#include <fstream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3> Triangle_mesh;
typedef CGAL::Surface_mesh_shortest_path_traits<Kernel, Triangle_mesh> Traits;
typedef CGAL::Surface_mesh_shortest_path<Traits> Surface_mesh_shortest_path;
typedef boost::graph_traits<Triangle_mesh> Graph_traits;
typedef Graph_traits::vertex_iterator vertex_iterator;
typedef Graph_traits::face_iterator face_iterator;

int main(int argc, char** argv)
{
    const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("hilbert_cube2_pds_100k_surface.obj");

    Triangle_mesh tmesh;
    if (!CGAL::IO::read_polygon_mesh(filename, tmesh))
    {
        std::cerr << "Invalid input file1." << std::endl;
        return EXIT_FAILURE;
    }

    const int target_face_index = 4880;
    face_iterator face_it = faces(tmesh).first;
    std::advance(face_it, target_face_index);
    // ... and define a barycentric coordinates inside the face
    Traits::Barycentric_coordinates face_location1 = { {0.46936893463134766,0.11540794372558594,0.4152231216430664} };
    Traits::Barycentric_coordinates face_location2 = { {0.16719023883342743, 0.47327518463134766,0.3595345914363861} };

    // construct a shortest path query object and add a source point
    Surface_mesh_shortest_path shortest_paths(tmesh);
    shortest_paths.add_source_point(*face_it, face_location1);
    std::cout << *face_it << std::endl;
    // For all vertices in the tmesh, compute the points of
    // the shortest path to the source point and write them
    // into a file readable using CGAL Lab
    std::ofstream output("shortest_paths.txt");
    face_iterator f_it = faces(tmesh).first;
    std::advance(f_it, 5749);
    std::vector<Traits::Point_3> points;
    std::cout << *f_it << std::endl;
    shortest_paths.shortest_path_points_to_source_points(*f_it, face_location2, std::back_inserter(points));

    // print the points
    output << points.size() << " ";
    for (std::size_t i = 0; i < points.size(); ++i)
        output << " " << points[i];
    output << std::endl;
}

Files

shortest_paths_bath.txt

shortest_paths_cube.txt

Model file.zip

Answer 1 · 2025-07-16T10:51:09.000Z

I only downloaded the model files. The bathtub consists of many patches that share edges. I did not check where your source and target point are, but they must be in the same patch, as the path cannot traverse boundaries. And if they lie both in the same patch the function will compute the shortest path in this patch.

Answer 2 · 2025-07-16T10:59:41.000Z

For the Hilbert data set, I asked @soesau to have a look as he devloped KSR. The mesh has only one connected component but self intersections.

Answer 3 · 2025-07-16T12:00:38.000Z

The mesh hilbert_cube2_pds_100k_surface.ply in the dataset linked in the kinetic surface reconstruction user manual was created by the researchers of that method. Our implementation creates a polygon mesh without self-intersections or duplicate points.

Here is the triangulated output of our KSR for the hilbert cube:
hilbert.zip

Answer 4 · 2025-07-18T02:00:21.000Z

May I ask how to handle these models? I have tried using 3D Alpha Wrapping to process the models, but this will lose some geometric fidelity and some larger models will take too long to run. I also used the following code to handle the self-intersection of the bathtub model, but it would result in an exception in intersection_impl.h. The following is the running code and the location where the exception occurs.

code:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Polygon_mesh_processing/self_intersections.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/remesh.h>

#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3                                     Point;
typedef CGAL::Surface_mesh<Kernel::Point_3> Triangle_mesh;

namespace PMP = CGAL::Polygon_mesh_processing;

int main(int argc, char** argv)
{
    const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("bathtub_0001.obj");

    Triangle_mesh tmesh;
    if (!PMP::IO::read_polygon_mesh(filename, tmesh))
    {
        std::cerr << "Invalid input file1." << std::endl;
        return EXIT_FAILURE;
    }

    bool has_self_intersections = PMP::does_self_intersect(tmesh);
    std::cout << "before：" << has_self_intersections << std::endl;

    PMP::experimental::autorefine(tmesh);
    //PMP::isotropic_remeshing(faces(tmesh),0, tmesh);

    bool intersections = PMP::does_self_intersect(tmesh);
    std::cout << "after：" << intersections << std::endl;

    CGAL::IO::write_polygon_mesh("bathtub_0002.obj", tmesh, CGAL::parameters::stream_precision(17));
}

exception:

if ( (collinear(s12[0], s12[1], s13[0]) && collinear(s12[0], s12[1], s13[1]) ) ||
     (collinear(s12[0], s12[1], s23[0]) && collinear(s12[0], s12[1], s23[1]) ) ||
     (collinear(s13[0], s13[1], s23[0]) && collinear(s13[0], s13[1], s23[1]) ) )
{
  throw Triple_intersection_exception();
}

Answer 5 · 2025-07-18T12:32:47.000Z

@sloriot can you have at the repair steps for the bathtub