Is there a way to make this shortest path algorithm faster?

Question

Using the CGAL lib, I'm trying to implement the Shortest Path methods.

I've been kind of successful, but the time it takes to map a path is not nearly acceptable, taking up to 1.5 seconds running in Release.

I'm aware that the input might be overwhelmingly big, having 50000 faces, but that is what I have to work with.

To be more detailed on what I'm trying to do is being able to draw a spline along the surface of a mesh by clicking in two different places and generating a path from them just like in the image:

My type definitions are:

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;
// default property maps
typedef boost::property_map<Triangle_mesh,
    boost::vertex_external_index_t>::type  Vertex_index_map;
typedef boost::property_map<Triangle_mesh,
    CGAL::halfedge_external_index_t>::type Halfedge_index_map;
typedef boost::property_map<Triangle_mesh,
    CGAL::face_external_index_t>::type     Face_index_map;
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::halfedge_iterator halfedge_iterator;
typedef Graph_traits::face_iterator face_iterator;

My code looks like the following:

Traits::Barycentric_coordinates src_face_location = { { p1.barycentric[2], p1.barycentric[0], p1.barycentric[1] } };
face_iterator src_face_it = faces(map->m_cgal_mesh).first;
std::advance(src_face_it, src_faceIndex);

map->m_shortest_paths->remove_all_source_points();
map->m_shortest_paths->add_source_point(*src_face_it, src_face_location);

Traits::Barycentric_coordinates dest_face_location = { { p2.barycentric[2], p2.barycentric[0], p2.barycentric[1] } };
face_iterator dest_face_it = faces(map->m_cgal_mesh).first;
std::advance(dest_face_it, dest_faceIndex);

std::vector<Traits::Point_3> cgal_points;
auto r = map->m_shortest_paths->shortest_path_points_to_source_points(*dest_face_it, dest_face_location, std::back_inserter(cgal_points));

points.resize(cgal_points.size(), 3);

for (int i = 0; i < cgal_points.size(); ++i) {
    auto const& p = cgal_points[i];
    points.row(i) = RowVector3d(p.x(), p.y(), p.z());
}

The process that takes 99% of the total time is on this line:

auto r = map->m_shortest_paths->shortest_path_points_to_source_points(*dest_face_it, dest_face_location, std::back_inserter(cgal_points));

Any idea on how to improve performance?

Answer 1

The CGAL docs state the shortest route is always a straight line when you would unfold the mesh on a 2D plane. The input for the shortest path algorithm is a vertex or plane with barycentric coordinates. You could map these input coordinates to a 2D texture which was mapped on your mesh. Draw a red line between start and end point on your texture. You will have to dig deeper on how to translate the vertices input coordinates into absolute XY coordinates in the texture. Also keep in mind that the shortest path could be running over the back of the mesh. Depending on how the texture is mapped it could be possible that you need to draw more than 1 line.