Blender  V3.3
node_geo_input_shortest_edge_paths.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include <queue>
4 
5 #include "BKE_curves.hh"
6 
7 #include "BLI_map.hh"
8 #include "BLI_math_vec_types.hh"
9 #include "BLI_set.hh"
10 
11 #include "DNA_mesh_types.h"
12 #include "DNA_meshdata_types.h"
13 
14 #include "node_geometry_util.hh"
15 
17 
19 {
20  b.add_input<decl::Bool>(N_("End Vertex")).default_value(false).hide_value().supports_field();
21  b.add_input<decl::Float>(N_("Edge Cost")).default_value(1.0f).hide_value().supports_field();
22  b.add_output<decl::Int>(N_("Next Vertex Index")).field_source();
23  b.add_output<decl::Float>(N_("Total Cost")).field_source();
24 }
25 
26 typedef std::pair<float, int> VertPriority;
27 
28 struct EdgeVertMap {
30 
32  {
33  const Span<MEdge> edges{mesh->medge, mesh->totedge};
34  edges_by_vertex_map.reinitialize(mesh->totvert);
35  for (const int edge_i : edges.index_range()) {
36  const MEdge &edge = edges[edge_i];
37  edges_by_vertex_map[edge.v1].append(edge_i);
38  edges_by_vertex_map[edge.v2].append(edge_i);
39  }
40  }
41 };
42 
43 static void shortest_paths(const Mesh *mesh,
44  EdgeVertMap &maps,
45  const IndexMask end_selection,
46  const VArray<float> &input_cost,
47  MutableSpan<int> r_next_index,
48  MutableSpan<float> r_cost)
49 {
51  const Span<MEdge> edges{mesh->medge, mesh->totedge};
53 
54  std::priority_queue<VertPriority, std::vector<VertPriority>, std::greater<VertPriority>> queue;
55 
56  for (const int start_vert_i : end_selection) {
57  r_cost[start_vert_i] = 0.0f;
58  queue.emplace(0.0f, start_vert_i);
59  }
60 
61  while (!queue.empty()) {
62  const float cost_i = queue.top().first;
63  const int vert_i = queue.top().second;
64  queue.pop();
65  if (visited[vert_i]) {
66  continue;
67  }
68  visited[vert_i] = true;
69  const Span<int> incident_edge_indices = maps.edges_by_vertex_map[vert_i];
70  for (const int edge_i : incident_edge_indices) {
71  const MEdge &edge = edges[edge_i];
72  const int neighbor_vert_i = edge.v1 + edge.v2 - vert_i;
73  if (visited[neighbor_vert_i]) {
74  continue;
75  }
76  const float edge_cost = std::max(0.0f, input_cost[edge_i]);
77  const float new_neighbour_cost = cost_i + edge_cost;
78  if (new_neighbour_cost < r_cost[neighbor_vert_i]) {
79  r_cost[neighbor_vert_i] = new_neighbour_cost;
80  r_next_index[neighbor_vert_i] = vert_i;
81  queue.emplace(new_neighbour_cost, neighbor_vert_i);
82  }
83  }
84  }
85 }
86 
88  private:
89  Field<bool> end_selection_;
90  Field<float> cost_;
91 
92  public:
94  : GeometryFieldInput(CPPType::get<int>(), "Shortest Edge Paths Next Vertex Field"),
95  end_selection_(end_selection),
96  cost_(cost)
97  {
99  }
100 
102  const eAttrDomain domain,
103  [[maybe_unused]] IndexMask mask) const final
104  {
105  if (component.type() != GEO_COMPONENT_TYPE_MESH) {
106  return {};
107  }
108  const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component);
109  const Mesh *mesh = mesh_component.get_for_read();
110  if (mesh == nullptr) {
111  return {};
112  }
114  fn::FieldEvaluator edge_evaluator{edge_context, mesh->totedge};
115  edge_evaluator.add(cost_);
116  edge_evaluator.evaluate();
117  const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0);
118 
120  fn::FieldEvaluator point_evaluator{point_context, mesh->totvert};
121  point_evaluator.add(end_selection_);
122  point_evaluator.evaluate();
123  const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0);
124 
125  Array<int> next_index(mesh->totvert, -1);
126  Array<float> cost(mesh->totvert, FLT_MAX);
127 
128  if (!end_selection.is_empty()) {
129  EdgeVertMap maps(mesh);
130  shortest_paths(mesh, maps, end_selection, input_cost, next_index, cost);
131  }
132  threading::parallel_for(next_index.index_range(), 1024, [&](const IndexRange range) {
133  for (const int i : range) {
134  if (next_index[i] == -1) {
135  next_index[i] = i;
136  }
137  }
138  });
139  return component.attributes()->adapt_domain<int>(
140  VArray<int>::ForContainer(std::move(next_index)), ATTR_DOMAIN_POINT, domain);
141  }
142 
143  uint64_t hash() const override
144  {
145  /* Some random constant hash. */
146  return 8466507837;
147  }
148 
149  bool is_equal_to(const fn::FieldNode &other) const override
150  {
151  if (const ShortestEdgePathsNextVertFieldInput *other_field =
152  dynamic_cast<const ShortestEdgePathsNextVertFieldInput *>(&other)) {
153  return other_field->end_selection_ == end_selection_ && other_field->cost_ == cost_;
154  }
155  return false;
156  }
157 };
158 
160  private:
161  Field<bool> end_selection_;
162  Field<float> cost_;
163 
164  public:
166  : GeometryFieldInput(CPPType::get<float>(), "Shortest Edge Paths Cost Field"),
167  end_selection_(end_selection),
168  cost_(cost)
169  {
170  category_ = Category::Generated;
171  }
172 
174  const eAttrDomain domain,
175  [[maybe_unused]] IndexMask mask) const final
176  {
177  if (component.type() != GEO_COMPONENT_TYPE_MESH) {
178  return {};
179  }
180  const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component);
181  const Mesh *mesh = mesh_component.get_for_read();
182  if (mesh == nullptr) {
183  return {};
184  }
186  fn::FieldEvaluator edge_evaluator{edge_context, mesh->totedge};
187  edge_evaluator.add(cost_);
188  edge_evaluator.evaluate();
189  const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0);
190 
192  fn::FieldEvaluator point_evaluator{point_context, mesh->totvert};
193  point_evaluator.add(end_selection_);
194  point_evaluator.evaluate();
195  const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0);
196 
197  Array<int> next_index(mesh->totvert, -1);
198  Array<float> cost(mesh->totvert, FLT_MAX);
199 
200  if (!end_selection.is_empty()) {
201  EdgeVertMap maps(mesh);
202  shortest_paths(mesh, maps, end_selection, input_cost, next_index, cost);
203  }
204  threading::parallel_for(cost.index_range(), 1024, [&](const IndexRange range) {
205  for (const int i : range) {
206  if (cost[i] == FLT_MAX) {
207  cost[i] = 0;
208  }
209  }
210  });
211  return component.attributes()->adapt_domain<float>(
212  VArray<float>::ForContainer(std::move(cost)), ATTR_DOMAIN_POINT, domain);
213  }
214 
215  uint64_t hash() const override
216  {
217  return get_default_hash_2(end_selection_, cost_);
218  }
219 
220  bool is_equal_to(const fn::FieldNode &other) const override
221  {
222  if (const ShortestEdgePathsCostFieldInput *other_field =
223  dynamic_cast<const ShortestEdgePathsCostFieldInput *>(&other)) {
224  return other_field->end_selection_ == end_selection_ && other_field->cost_ == cost_;
225  }
226  return false;
227  }
228 };
229 
231 {
232  Field<bool> end_selection = params.extract_input<Field<bool>>("End Vertex");
233  Field<float> cost = params.extract_input<Field<float>>("Edge Cost");
234 
235  Field<int> next_vert_field{
236  std::make_shared<ShortestEdgePathsNextVertFieldInput>(end_selection, cost)};
237  Field<float> cost_field{std::make_shared<ShortestEdgePathsCostFieldInput>(end_selection, cost)};
238  params.set_output("Next Vertex Index", std::move(next_vert_field));
239  params.set_output("Total Cost", std::move(cost_field));
240 }
241 
242 } // namespace blender::nodes::node_geo_input_shortest_edge_paths_cc
243 
245 {
247 
248  static bNodeType ntype;
249 
251  &ntype, GEO_NODE_INPUT_SHORTEST_EDGE_PATHS, "Shortest Edge Paths", NODE_CLASS_INPUT);
254  nodeRegisterType(&ntype);
255 }
typedef float(TangentPoint)[2]
eAttrDomain
Definition: BKE_attribute.h:25
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
@ ATTR_DOMAIN_EDGE
Definition: BKE_attribute.h:28
Low-level operations for curves.
@ GEO_COMPONENT_TYPE_MESH
#define GEO_NODE_INPUT_SHORTEST_EDGE_PATHS
Definition: BKE_node.h:1509
#define NODE_CLASS_INPUT
Definition: BKE_node.h:345
void nodeRegisterType(struct bNodeType *ntype)
Definition: node.cc:1357
#define final(a, b, c)
Definition: BLI_hash.h:21
static uint8 component(Color32 c, uint i)
Definition: ColorBlock.cpp:108
const Mesh * get_for_read() const
IndexRange index_range() const
Definition: BLI_array.hh:348
bool is_empty() const
static VArray ForContainer(ContainerT container)
GVArray get_varray_for_context(const GeometryComponent &component, const eAttrDomain domain, [[maybe_unused]] IndexMask mask) const final
GVArray get_varray_for_context(const GeometryComponent &component, const eAttrDomain domain, [[maybe_unused]] IndexMask mask) const final
Set< ComponentNode * > visited
SyclQueue * queue
static float verts[][3]
uiWidgetBaseParameters params[MAX_WIDGET_BASE_BATCH]
ccl_device_inline float4 mask(const int4 &mask, const float4 &a)
Definition: math_float4.h:513
static void shortest_paths(const Mesh *mesh, EdgeVertMap &maps, const IndexMask end_selection, const VArray< float > &input_cost, MutableSpan< int > r_next_index, MutableSpan< float > r_cost)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
uint64_t get_default_hash_2(const T1 &v1, const T2 &v2)
Definition: BLI_hash.hh:223
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
void register_node_type_geo_input_shortest_edge_paths()
void geo_node_type_base(bNodeType *ntype, int type, const char *name, short nclass)
unsigned __int64 uint64_t
Definition: stdint.h:90
struct MEdge * medge
struct MVert * mvert
int totedge
int totvert
Defines a node type.
Definition: BKE_node.h:226
NodeGeometryExecFunction geometry_node_execute
Definition: BKE_node.h:316
NodeDeclareFunction declare
Definition: BKE_node.h:324
float max
#define N_(msgid)