Lagrange
compute_dijkstra_distance.h
1/*
2 * Copyright 2017 Adobe. All rights reserved.
3 * This file is licensed to you under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License. You may obtain a copy
5 * of the License at http://www.apache.org/licenses/LICENSE-2.0
6 *
7 * Unless required by applicable law or agreed to in writing, software distributed under
8 * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR REPRESENTATIONS
9 * OF ANY KIND, either express or implied. See the License for the specific language
10 * governing permissions and limitations under the License.
11 */
12#pragma once
13
14
15#include <cassert>
16#include <limits>
17#include <list>
18#include <queue>
19#include <vector>
20
21#include <lagrange/Mesh.h>
22#include <lagrange/common.h>
23
24namespace lagrange {
25LAGRANGE_LEGACY_INLINE
26namespace legacy {
27
28
29template <typename MeshType>
30std::list<std::pair<typename MeshType::Index, typename MeshType::Scalar>> compute_dijkstra_distance(
31 MeshType& mesh,
32 typename MeshType::Index seed_facet_id,
33 const Eigen::Matrix<typename MeshType::Scalar, 3, 1>& bc,
34 typename MeshType::Scalar radius = 0.0)
35{
36 using Scalar = typename MeshType::Scalar;
37 if (mesh.get_dim() != 3) {
38 throw std::runtime_error("Input mesh must be 3D mesh.");
39 }
40 if (mesh.get_vertex_per_facet() != 3) {
41 throw std::runtime_error("Input mesh is not triangle mesh");
42 }
43 if (!mesh.is_connectivity_initialized()) {
44 mesh.initialize_connectivity();
45 }
46
47 using Index = typename MeshType::Index;
48 using FacetType = Eigen::Matrix<Index, 3, 1>;
49 using VertexType = typename MeshType::VertexType;
50 using AttributeArray = typename MeshType::AttributeArray;
51
52 if (radius <= 0.0) {
53 radius = std::numeric_limits<Scalar>::max();
54 }
55 const Index num_facets = mesh.get_num_facets();
56 const Index num_vertices = mesh.get_num_vertices();
57 const auto& vertices = mesh.get_vertices();
58 const auto& facets = mesh.get_facets();
59 la_runtime_assert(seed_facet_id < num_facets);
60 const FacetType seed_facet = facets.row(seed_facet_id);
61 const VertexType seed_point = vertices.row(seed_facet[0]) * bc[0] +
62 vertices.row(seed_facet[1]) * bc[1] +
63 vertices.row(seed_facet[2]) * bc[2];
64
65 using Entry = std::pair<Index, Scalar>;
66 auto comp = [](const Entry& e1, const Entry& e2) { return e1.second > e2.second; };
67 std::priority_queue<Entry, std::vector<Entry>, decltype(comp)> Q(comp);
68 AttributeArray dist(num_vertices, 1);
69 dist.setConstant(-1);
70 Q.push({seed_facet[0], (vertices.row(seed_facet[0]) - seed_point).norm()});
71 Q.push({seed_facet[1], (vertices.row(seed_facet[1]) - seed_point).norm()});
72 Q.push({seed_facet[2], (vertices.row(seed_facet[2]) - seed_point).norm()});
73
74 std::list<Entry> involved_vts;
75 while (!Q.empty()) {
76 Entry entry = Q.top();
77 involved_vts.push_back(entry);
78 Q.pop();
79 Scalar curr_dist = dist(entry.first, 0);
80
81 if (curr_dist < 0 || entry.second < curr_dist) {
82 dist(entry.first, 0) = entry.second;
83 const auto& adj_vertices = mesh.get_vertices_adjacent_to_vertex(entry.first);
84 for (const auto& vj : adj_vertices) {
85 Scalar d = entry.second + (vertices.row(vj) - vertices.row(entry.first)).norm();
86 if (d < radius) {
87 Scalar next_dist = dist(vj, 0);
88 if (next_dist < 0 || d < next_dist) {
89 Q.push({vj, d});
90 }
91 }
92 }
93 }
94 }
95
96 mesh.add_vertex_attribute("dijkstra_distance");
97 mesh.import_vertex_attribute("dijkstra_distance", dist);
98 return involved_vts;
99}
100
101} // namespace legacy
102} // namespace lagrange
Definition: Mesh.h:48
std::optional< std::vector< Index > > compute_dijkstra_distance(SurfaceMesh< Scalar, Index > &mesh, const DijkstraDistanceOptions< Scalar, Index > &options={})
Computes dijkstra distance from a seed facet.
Definition: compute_dijkstra_distance.cpp:24
#define la_runtime_assert(...)
Runtime assertion check.
Definition: assert.h:169
Main namespace for Lagrange.
Definition: AABBIGL.h:30