Blender  V3.3
node_geo_dual_mesh.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_task.hh"
4 
5 #include "DNA_mesh_types.h"
6 #include "DNA_meshdata_types.h"
7 
8 #include "BKE_attribute_math.hh"
9 #include "BKE_mesh.h"
10 
11 #include "node_geometry_util.hh"
12 
14 
16 {
17  b.add_input<decl::Geometry>("Mesh").supported_type(GEO_COMPONENT_TYPE_MESH);
18  b.add_input<decl::Bool>("Keep Boundaries")
19  .default_value(false)
20  .description(
21  "Keep non-manifold boundaries of the input mesh in place by avoiding the dual "
22  "transformation there");
23  b.add_output<decl::Geometry>("Dual Mesh");
24 }
25 
26 enum class EdgeType : int8_t {
27  Loose = 0, /* No polygons connected to it. */
28  Boundary = 1, /* An edge connected to exactly one polygon. */
29  Normal = 2, /* A normal edge (connected to two polygons). */
30  NonManifold = 3, /* An edge connected to more than two polygons. */
31 };
32 
34 {
35  switch (old_type) {
36  case EdgeType::Loose:
37  return EdgeType::Boundary;
38  case EdgeType::Boundary:
39  return EdgeType::Normal;
40  case EdgeType::Normal:
42  return EdgeType::NonManifold;
43  }
45  return EdgeType::Loose;
46 }
47 
48 enum class VertexType : int8_t {
49  Loose = 0, /* Either no edges connected or only loose edges connected. */
50  Normal = 1, /* A normal vertex. */
51  Boundary = 2, /* A vertex on a boundary edge. */
52  NonManifold = 3, /* A vertex on a non-manifold edge. */
53 };
54 
56 {
57  switch (old_type) {
58  case VertexType::Loose:
59  return VertexType::Normal;
60  case VertexType::Normal:
61  return VertexType::Boundary;
65  }
67  return VertexType::Loose;
68 }
69 
70 /* Copy only where vertex_types is 'normal'. If keep boundaries is selected, also copy from
71  * boundary vertices. */
72 template<typename T>
74  MutableSpan<T> r_data,
75  const Span<VertexType> vertex_types,
76  const bool keep_boundaries)
77 {
78  if (keep_boundaries) {
79  int out_i = 0;
80  for (const int i : data.index_range()) {
81  if (ELEM(vertex_types[i], VertexType::Normal, VertexType::Boundary)) {
82  r_data[out_i] = data[i];
83  out_i++;
84  }
85  }
86  }
87  else {
88  int out_i = 0;
89  for (const int i : data.index_range()) {
90  if (vertex_types[i] == VertexType::Normal) {
91  r_data[out_i] = data[i];
92  out_i++;
93  }
94  }
95  }
96 }
97 
98 template<typename T>
100  MutableSpan<T> r_data,
101  const Span<std::pair<int, int>> new_to_old_map)
102 {
103  for (const std::pair<int, int> &pair : new_to_old_map) {
104  r_data[pair.first] = data[pair.second];
105  }
106 }
107 
108 /* Copy using the map. */
109 template<typename T>
111  MutableSpan<T> r_data,
112  const Span<int> new_to_old_map)
113 {
114  for (const int i : r_data.index_range()) {
115  const int old_i = new_to_old_map[i];
116  r_data[i] = data[old_i];
117  }
118 }
119 
140  const Map<AttributeIDRef, AttributeKind> &attributes,
141  const Span<VertexType> vertex_types,
142  const bool keep_boundaries,
143  const Span<int> new_to_old_edges_map,
144  const Span<int> new_to_old_face_corners_map,
145  const Span<std::pair<int, int>> boundary_vertex_to_relevant_face_map,
146  const AttributeAccessor src_attributes,
147  MutableAttributeAccessor dst_attributes)
148 {
149  for (Map<AttributeIDRef, AttributeKind>::Item entry : attributes.items()) {
150  const AttributeIDRef attribute_id = entry.key;
151  GAttributeReader src_attribute = src_attributes.lookup(attribute_id);
152  if (!src_attribute) {
153  continue;
154  }
155 
156  eAttrDomain out_domain;
157  if (src_attribute.domain == ATTR_DOMAIN_FACE) {
158  out_domain = ATTR_DOMAIN_POINT;
159  }
160  else if (src_attribute.domain == ATTR_DOMAIN_POINT) {
161  out_domain = ATTR_DOMAIN_FACE;
162  }
163  else {
164  /* Edges and Face Corners. */
165  out_domain = src_attribute.domain;
166  }
168  src_attribute.varray.type());
169  GSpanAttributeWriter dst_attribute = dst_attributes.lookup_or_add_for_write_only_span(
170  attribute_id, out_domain, data_type);
171 
172  if (!dst_attribute) {
173  continue;
174  }
175 
176  attribute_math::convert_to_static_type(data_type, [&](auto dummy) {
177  using T = decltype(dummy);
178  VArraySpan<T> span{src_attribute.varray.typed<T>()};
179  MutableSpan<T> dst_span = dst_attribute.span.typed<T>();
180  if (src_attribute.domain == ATTR_DOMAIN_FACE) {
181  dst_span.take_front(span.size()).copy_from(span);
182  if (keep_boundaries) {
183  copy_data_based_on_pairs(span, dst_span, boundary_vertex_to_relevant_face_map);
184  }
185  }
186  else if (src_attribute.domain == ATTR_DOMAIN_POINT) {
187  copy_data_based_on_vertex_types(span, dst_span, vertex_types, keep_boundaries);
188  }
189  else if (src_attribute.domain == ATTR_DOMAIN_EDGE) {
190  copy_data_based_on_new_to_old_map(span, dst_span, new_to_old_edges_map);
191  }
192  else {
193  copy_data_based_on_new_to_old_map(span, dst_span, new_to_old_face_corners_map);
194  }
195  });
196  dst_attribute.finish();
197  }
198 }
199 
206 static void calc_boundaries(const Mesh &mesh,
207  MutableSpan<VertexType> r_vertex_types,
208  MutableSpan<EdgeType> r_edge_types)
209 {
210  BLI_assert(r_vertex_types.size() == mesh.totvert);
211  BLI_assert(r_edge_types.size() == mesh.totedge);
212  r_vertex_types.fill(VertexType::Loose);
213  r_edge_types.fill(EdgeType::Loose);
214 
215  /* Add up the number of polys connected to each edge. */
216  for (const int i : IndexRange(mesh.totpoly)) {
217  const MPoly &poly = mesh.mpoly[i];
218  for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
219  r_edge_types[loop.e] = get_edge_type_with_added_neighbor(r_edge_types[loop.e]);
220  }
221  }
222 
223  /* Update vertices. */
224  for (const int i : IndexRange(mesh.totedge)) {
225  const EdgeType edge_type = r_edge_types[i];
226  if (edge_type == EdgeType::Loose) {
227  continue;
228  }
229  const MEdge &edge = mesh.medge[i];
230  if (edge_type == EdgeType::Boundary) {
231  r_vertex_types[edge.v1] = get_vertex_type_with_added_neighbor(r_vertex_types[edge.v1]);
232  r_vertex_types[edge.v2] = get_vertex_type_with_added_neighbor(r_vertex_types[edge.v2]);
233  }
234  else if (edge_type >= EdgeType::NonManifold) {
235  r_vertex_types[edge.v1] = VertexType::NonManifold;
236  r_vertex_types[edge.v2] = VertexType::NonManifold;
237  }
238  }
239 
240  /* Normal verts are on a normal edge, and not on boundary edges or non-manifold edges. */
241  for (const int i : IndexRange(mesh.totedge)) {
242  const EdgeType edge_type = r_edge_types[i];
243  if (edge_type == EdgeType::Normal) {
244  const MEdge &edge = mesh.medge[i];
245  if (r_vertex_types[edge.v1] == VertexType::Loose) {
246  r_vertex_types[edge.v1] = VertexType::Normal;
247  }
248  if (r_vertex_types[edge.v2] == VertexType::Loose) {
249  r_vertex_types[edge.v2] = VertexType::Normal;
250  }
251  }
252  }
253 }
254 
258 static void create_vertex_poly_map(const Mesh &mesh,
259  MutableSpan<Vector<int>> r_vertex_poly_indices)
260 {
261  for (const int i : IndexRange(mesh.totpoly)) {
262  const MPoly &poly = mesh.mpoly[i];
263  for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
264  r_vertex_poly_indices[loop.v].append(i);
265  }
266  }
267 }
268 
324 static bool sort_vertex_polys(const Mesh &mesh,
325  const int vertex_index,
326  const bool boundary_vertex,
327  const Span<EdgeType> edge_types,
328  MutableSpan<int> connected_polygons,
329  MutableSpan<int> r_shared_edges,
330  MutableSpan<int> r_sorted_corners)
331 {
332  if (connected_polygons.size() <= 2 && (!boundary_vertex || connected_polygons.size() == 0)) {
333  return true;
334  }
335 
336  /* For each polygon store the two corners whose edge contains the vertex. */
337  Array<std::pair<int, int>> poly_vertex_corners(connected_polygons.size());
338  for (const int i : connected_polygons.index_range()) {
339  const MPoly &poly = mesh.mpoly[connected_polygons[i]];
340  bool first_edge_done = false;
341  for (const int loop_index : IndexRange(poly.loopstart, poly.totloop)) {
342  const MLoop &loop = mesh.mloop[loop_index];
343  if (mesh.medge[loop.e].v1 == vertex_index || mesh.medge[loop.e].v2 == vertex_index) {
344  if (!first_edge_done) {
345  poly_vertex_corners[i].first = loop_index;
346  first_edge_done = true;
347  }
348  else {
349  poly_vertex_corners[i].second = loop_index;
350  break;
351  }
352  }
353  }
354  }
355 
356  int shared_edge_i = -1;
357  /* Determine first polygon and orientation. For now the orientation of the whole loop depends
358  * on the one polygon we chose as first. It's probably not worth it to check every polygon in
359  * the loop to determine the 'average' orientation. */
360  if (boundary_vertex) {
361  /* Our first polygon needs to be one which has a boundary edge. */
362  for (const int i : connected_polygons.index_range()) {
363  const MLoop &first_loop = mesh.mloop[poly_vertex_corners[i].first];
364  const MLoop &second_loop = mesh.mloop[poly_vertex_corners[i].second];
365  if (edge_types[first_loop.e] == EdgeType::Boundary && first_loop.v == vertex_index) {
366  shared_edge_i = second_loop.e;
367  r_sorted_corners[0] = poly_vertex_corners[i].first;
368  std::swap(connected_polygons[i], connected_polygons[0]);
369  std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
370  break;
371  }
372  if (edge_types[second_loop.e] == EdgeType::Boundary && second_loop.v == vertex_index) {
373  shared_edge_i = first_loop.e;
374  r_sorted_corners[0] = poly_vertex_corners[i].second;
375  std::swap(connected_polygons[i], connected_polygons[0]);
376  std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
377  break;
378  }
379  }
380  if (shared_edge_i == -1) {
381  /* The rotation is inconsistent between the two polygons on the boundary. Just choose one
382  * of the polygon's orientation. */
383  for (const int i : connected_polygons.index_range()) {
384  const MLoop &first_loop = mesh.mloop[poly_vertex_corners[i].first];
385  const MLoop &second_loop = mesh.mloop[poly_vertex_corners[i].second];
386  if (edge_types[first_loop.e] == EdgeType::Boundary) {
387  shared_edge_i = second_loop.e;
388  r_sorted_corners[0] = poly_vertex_corners[i].first;
389  std::swap(connected_polygons[i], connected_polygons[0]);
390  std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
391  break;
392  }
393  if (edge_types[second_loop.e] == EdgeType::Boundary) {
394  shared_edge_i = first_loop.e;
395  r_sorted_corners[0] = poly_vertex_corners[i].second;
396  std::swap(connected_polygons[i], connected_polygons[0]);
397  std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
398  break;
399  }
400  }
401  }
402  }
403  else {
404  /* Any polygon can be the first. Just need to check the orientation. */
405  const MLoop &first_loop = mesh.mloop[poly_vertex_corners[0].first];
406  const MLoop &second_loop = mesh.mloop[poly_vertex_corners[0].second];
407  if (first_loop.v == vertex_index) {
408  shared_edge_i = second_loop.e;
409  r_sorted_corners[0] = poly_vertex_corners[0].first;
410  }
411  else {
412  r_sorted_corners[0] = poly_vertex_corners[0].second;
413  shared_edge_i = first_loop.e;
414  }
415  }
416  BLI_assert(shared_edge_i != -1);
417 
418  for (const int i : IndexRange(connected_polygons.size() - 1)) {
419  r_shared_edges[i] = shared_edge_i;
420 
421  /* Look at the other polys to see if it has this shared edge. */
422  int j = i + 1;
423  for (; j < connected_polygons.size(); ++j) {
424  const MLoop &first_loop = mesh.mloop[poly_vertex_corners[j].first];
425  const MLoop &second_loop = mesh.mloop[poly_vertex_corners[j].second];
426  if (first_loop.e == shared_edge_i) {
427  r_sorted_corners[i + 1] = poly_vertex_corners[j].first;
428  shared_edge_i = second_loop.e;
429  break;
430  }
431  if (second_loop.e == shared_edge_i) {
432  r_sorted_corners[i + 1] = poly_vertex_corners[j].second;
433  shared_edge_i = first_loop.e;
434  break;
435  }
436  }
437  if (j == connected_polygons.size()) {
438  /* The vertex is not manifold because the polygons around the vertex don't form a loop, and
439  * hence can't be sorted. */
440  return false;
441  }
442 
443  std::swap(connected_polygons[i + 1], connected_polygons[j]);
444  std::swap(poly_vertex_corners[i + 1], poly_vertex_corners[j]);
445  }
446 
447  if (!boundary_vertex) {
448  /* Shared edge between first and last polygon. */
449  r_shared_edges.last() = shared_edge_i;
450  }
451  return true;
452 }
453 
457 static void boundary_edge_on_poly(const MPoly &poly,
458  const Mesh &mesh,
459  const int vertex_index,
460  const Span<EdgeType> edge_types,
461  int &r_edge)
462 {
463  for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
464  if (edge_types[loop.e] == EdgeType::Boundary) {
465  const MEdge &edge = mesh.medge[loop.e];
466  if (edge.v1 == vertex_index || edge.v2 == vertex_index) {
467  r_edge = loop.e;
468  return;
469  }
470  }
471  }
472 }
473 
478 static void boundary_edges_on_poly(const MPoly &poly,
479  const Mesh &mesh,
480  const int vertex_index,
481  const Span<EdgeType> edge_types,
482  int &r_edge1,
483  int &r_edge2)
484 {
485  bool edge1_done = false;
486  /* This is set to true if the order in which we encounter the two edges is inconsistent with the
487  * orientation of the polygon. */
488  bool needs_swap = false;
489  for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
490  if (edge_types[loop.e] == EdgeType::Boundary) {
491  const MEdge &edge = mesh.medge[loop.e];
492  if (edge.v1 == vertex_index || edge.v2 == vertex_index) {
493  if (edge1_done) {
494  if (needs_swap) {
495  r_edge2 = r_edge1;
496  r_edge1 = loop.e;
497  }
498  else {
499  r_edge2 = loop.e;
500  }
501  return;
502  }
503  r_edge1 = loop.e;
504  edge1_done = true;
505  if (loop.v == vertex_index) {
506  needs_swap = true;
507  }
508  }
509  }
510  }
511 }
512 
513 static void add_edge(const Mesh &mesh,
514  const int old_edge_i,
515  const int v1,
516  const int v2,
517  Vector<int> &new_to_old_edges_map,
518  Vector<MEdge> &new_edges,
519  Vector<int> &loop_edges)
520 {
521  MEdge new_edge = MEdge(mesh.medge[old_edge_i]);
522  new_edge.v1 = v1;
523  new_edge.v2 = v2;
524  const int new_edge_i = new_edges.size();
525  new_to_old_edges_map.append(old_edge_i);
526  new_edges.append(new_edge);
527  loop_edges.append(new_edge_i);
528 }
529 
530 /* Returns true if the vertex is connected only to the two polygons and is not on the boundary. */
531 static bool vertex_needs_dissolving(const int vertex,
532  const int first_poly_index,
533  const int second_poly_index,
534  const Span<VertexType> vertex_types,
535  const Span<Vector<int>> vertex_poly_indices)
536 {
537  /* Order is guaranteed to be the same because 2poly verts that are not on the boundary are
538  * ignored in `sort_vertex_polys`. */
539  return (vertex_types[vertex] != VertexType::Boundary &&
540  vertex_poly_indices[vertex].size() == 2 &&
541  vertex_poly_indices[vertex][0] == first_poly_index &&
542  vertex_poly_indices[vertex][1] == second_poly_index);
543 }
544 
552 static void dissolve_redundant_verts(const Mesh &mesh,
553  const Span<Vector<int>> vertex_poly_indices,
554  MutableSpan<VertexType> vertex_types,
555  MutableSpan<int> old_to_new_edges_map,
556  Vector<MEdge> &new_edges,
557  Vector<int> &new_to_old_edges_map)
558 {
559  for (const int vert_i : IndexRange(mesh.totvert)) {
560  if (vertex_poly_indices[vert_i].size() != 2 || vertex_types[vert_i] != VertexType::Normal) {
561  continue;
562  }
563  const int first_poly_index = vertex_poly_indices[vert_i][0];
564  const int second_poly_index = vertex_poly_indices[vert_i][1];
565  const int new_edge_index = new_edges.size();
566  bool edge_created = false;
567  const MPoly &poly = mesh.mpoly[first_poly_index];
568  for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
569  const MEdge &edge = mesh.medge[loop.e];
570  const int v1 = edge.v1;
571  const int v2 = edge.v2;
572  bool mark_edge = false;
574  v1, first_poly_index, second_poly_index, vertex_types, vertex_poly_indices)) {
575  /* This vertex is now 'removed' and should be ignored elsewhere. */
576  vertex_types[v1] = VertexType::Loose;
577  mark_edge = true;
578  }
580  v2, first_poly_index, second_poly_index, vertex_types, vertex_poly_indices)) {
581  /* This vertex is now 'removed' and should be ignored elsewhere. */
582  vertex_types[v2] = VertexType::Loose;
583  mark_edge = true;
584  }
585  if (mark_edge) {
586  if (!edge_created) {
587  MEdge new_edge = MEdge(edge);
588  /* The vertex indices in the dual mesh are the polygon indices of the input mesh. */
589  new_edge.v1 = first_poly_index;
590  new_edge.v2 = second_poly_index;
591  new_to_old_edges_map.append(loop.e);
592  new_edges.append(new_edge);
593  edge_created = true;
594  }
595  old_to_new_edges_map[loop.e] = new_edge_index;
596  }
597  }
598  }
599 }
600 
615 static void calc_dual_mesh(GeometrySet &geometry_set,
616  const MeshComponent &in_component,
617  const bool keep_boundaries)
618 {
619  const Mesh &mesh_in = *in_component.get_for_read();
620 
623  {GEO_COMPONENT_TYPE_MESH}, GEO_COMPONENT_TYPE_MESH, false, attributes);
624 
625  Array<VertexType> vertex_types(mesh_in.totvert);
626  Array<EdgeType> edge_types(mesh_in.totedge);
627  calc_boundaries(mesh_in, vertex_types, edge_types);
628  /* Stores the indices of the polygons connected to the vertex. Because the polygons are looped
629  * over in order of their indices, the polygon's indices will be sorted in ascending order.
630  * (This can change once they are sorted using `sort_vertex_polys`). */
631  Array<Vector<int>> vertex_poly_indices(mesh_in.totvert);
632  Array<Array<int>> vertex_shared_edges(mesh_in.totvert);
633  Array<Array<int>> vertex_corners(mesh_in.totvert);
634  create_vertex_poly_map(mesh_in, vertex_poly_indices);
635  threading::parallel_for(vertex_poly_indices.index_range(), 512, [&](IndexRange range) {
636  for (const int i : range) {
637  if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
638  (!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {
639  /* Bad vertex that we can't work with. */
640  continue;
641  }
642  MutableSpan<int> loop_indices = vertex_poly_indices[i];
643  Array<int> sorted_corners(loop_indices.size());
644  bool vertex_ok = true;
645  if (vertex_types[i] == VertexType::Normal) {
646  Array<int> shared_edges(loop_indices.size());
647  vertex_ok = sort_vertex_polys(
648  mesh_in, i, false, edge_types, loop_indices, shared_edges, sorted_corners);
649  vertex_shared_edges[i] = std::move(shared_edges);
650  }
651  else {
652  Array<int> shared_edges(loop_indices.size() - 1);
653  vertex_ok = sort_vertex_polys(
654  mesh_in, i, true, edge_types, loop_indices, shared_edges, sorted_corners);
655  vertex_shared_edges[i] = std::move(shared_edges);
656  }
657  if (!vertex_ok) {
658  /* The sorting failed which means that the vertex is non-manifold and should be ignored
659  * further on. */
660  vertex_types[i] = VertexType::NonManifold;
661  continue;
662  }
663  vertex_corners[i] = std::move(sorted_corners);
664  }
665  });
666 
667  Vector<float3> vertex_positions(mesh_in.totpoly);
668  for (const int i : IndexRange(mesh_in.totpoly)) {
669  const MPoly poly = mesh_in.mpoly[i];
671  &poly, &mesh_in.mloop[poly.loopstart], mesh_in.mvert, vertex_positions[i]);
672  }
673 
674  Array<int> boundary_edge_midpoint_index;
675  if (keep_boundaries) {
676  /* Only initialize when we actually need it. */
677  boundary_edge_midpoint_index.reinitialize(mesh_in.totedge);
678  /* We need to add vertices at the centers of boundary edges. */
679  for (const int i : IndexRange(mesh_in.totedge)) {
680  if (edge_types[i] == EdgeType::Boundary) {
681  float3 mid;
682  const MEdge &edge = mesh_in.medge[i];
683  mid_v3_v3v3(mid, mesh_in.mvert[edge.v1].co, mesh_in.mvert[edge.v2].co);
684  boundary_edge_midpoint_index[i] = vertex_positions.size();
685  vertex_positions.append(mid);
686  }
687  }
688  }
689 
690  Vector<int> loop_lengths;
691  Vector<int> loops;
692  Vector<int> loop_edges;
693  Vector<MEdge> new_edges;
694  /* These are used to transfer attributes. */
695  Vector<int> new_to_old_face_corners_map;
696  Vector<int> new_to_old_edges_map;
697  /* Stores the index of the vertex in the dual and the face it should get the attribute from. */
698  Vector<std::pair<int, int>> boundary_vertex_to_relevant_face_map;
699  /* Since each edge in the dual (except the ones created with keep boundaries) comes from
700  * exactly one edge in the original, we can use this array to keep track of whether it still
701  * needs to be created or not. If it's not -1 it gives the index in `new_edges` of the dual
702  * edge. The edges coming from preserving the boundaries only get added once anyway, so we
703  * don't need a hash-map for that. */
704  Array<int> old_to_new_edges_map(mesh_in.totedge);
705  old_to_new_edges_map.fill(-1);
706 
707  /* This is necessary to prevent duplicate edges from being created, but will likely not do
708  * anything for most meshes. */
709  dissolve_redundant_verts(mesh_in,
710  vertex_poly_indices,
711  vertex_types,
712  old_to_new_edges_map,
713  new_edges,
714  new_to_old_edges_map);
715 
716  for (const int i : IndexRange(mesh_in.totvert)) {
717  if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
718  (!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {
719  /* Bad vertex that we can't work with. */
720  continue;
721  }
722 
723  Vector<int> loop_indices = vertex_poly_indices[i];
724  Span<int> shared_edges = vertex_shared_edges[i];
725  Span<int> sorted_corners = vertex_corners[i];
726  if (vertex_types[i] == VertexType::Normal) {
727  if (loop_indices.size() <= 2) {
728  /* We can't make a polygon from 2 vertices. */
729  continue;
730  }
731 
732  /* Add edges in the loop. */
733  for (const int i : shared_edges.index_range()) {
734  const int old_edge_i = shared_edges[i];
735  if (old_to_new_edges_map[old_edge_i] == -1) {
736  /* This edge has not been created yet. */
737  MEdge new_edge = MEdge(mesh_in.medge[old_edge_i]);
738  new_edge.v1 = loop_indices[i];
739  new_edge.v2 = loop_indices[(i + 1) % loop_indices.size()];
740  new_to_old_edges_map.append(old_edge_i);
741  old_to_new_edges_map[old_edge_i] = new_edges.size();
742  new_edges.append(new_edge);
743  }
744  loop_edges.append(old_to_new_edges_map[old_edge_i]);
745  }
746 
747  new_to_old_face_corners_map.extend(sorted_corners);
748  }
749  else {
774  /* Add the edges in between the polys. */
775  for (const int i : shared_edges.index_range()) {
776  const int old_edge_i = shared_edges[i];
777  if (old_to_new_edges_map[old_edge_i] == -1) {
778  /* This edge has not been created yet. */
779  MEdge new_edge = MEdge(mesh_in.medge[old_edge_i]);
780  new_edge.v1 = loop_indices[i];
781  new_edge.v2 = loop_indices[i + 1];
782  new_to_old_edges_map.append(old_edge_i);
783  old_to_new_edges_map[old_edge_i] = new_edges.size();
784  new_edges.append(new_edge);
785  }
786  loop_edges.append(old_to_new_edges_map[old_edge_i]);
787  }
788 
789  new_to_old_face_corners_map.extend(sorted_corners);
790 
791  /* Add the vertex and the midpoints of the two boundary edges to the loop. */
792 
793  /* Get the boundary edges. */
794  int edge1;
795  int edge2;
796  if (loop_indices.size() >= 2) {
797  /* The first boundary edge is at the end of the chain of polygons. */
798  boundary_edge_on_poly(mesh_in.mpoly[loop_indices.last()], mesh_in, i, edge_types, edge1);
799  boundary_edge_on_poly(mesh_in.mpoly[loop_indices.first()], mesh_in, i, edge_types, edge2);
800  }
801  else {
802  /* If there is only one polygon both edges are in that polygon. */
804  mesh_in.mpoly[loop_indices[0]], mesh_in, i, edge_types, edge1, edge2);
805  }
806 
807  const int last_face_center = loop_indices.last();
808  loop_indices.append(boundary_edge_midpoint_index[edge1]);
809  new_to_old_face_corners_map.append(sorted_corners.last());
810  const int first_midpoint = loop_indices.last();
811  if (old_to_new_edges_map[edge1] == -1) {
812  add_edge(mesh_in,
813  edge1,
814  last_face_center,
815  first_midpoint,
816  new_to_old_edges_map,
817  new_edges,
818  loop_edges);
819  old_to_new_edges_map[edge1] = new_edges.size() - 1;
820  boundary_vertex_to_relevant_face_map.append(std::pair(first_midpoint, last_face_center));
821  }
822  else {
823  loop_edges.append(old_to_new_edges_map[edge1]);
824  }
825  loop_indices.append(vertex_positions.size());
826  /* This is sort of arbitrary, but interpolating would be a lot harder to do. */
827  new_to_old_face_corners_map.append(sorted_corners.first());
828  boundary_vertex_to_relevant_face_map.append(
829  std::pair(loop_indices.last(), last_face_center));
830  vertex_positions.append(mesh_in.mvert[i].co);
831  const int boundary_vertex = loop_indices.last();
832  add_edge(mesh_in,
833  edge1,
834  first_midpoint,
835  boundary_vertex,
836  new_to_old_edges_map,
837  new_edges,
838  loop_edges);
839 
840  loop_indices.append(boundary_edge_midpoint_index[edge2]);
841  new_to_old_face_corners_map.append(sorted_corners.first());
842  const int second_midpoint = loop_indices.last();
843  add_edge(mesh_in,
844  edge2,
845  boundary_vertex,
846  second_midpoint,
847  new_to_old_edges_map,
848  new_edges,
849  loop_edges);
850 
851  if (old_to_new_edges_map[edge2] == -1) {
852  const int first_face_center = loop_indices.first();
853  add_edge(mesh_in,
854  edge2,
855  second_midpoint,
856  first_face_center,
857  new_to_old_edges_map,
858  new_edges,
859  loop_edges);
860  old_to_new_edges_map[edge2] = new_edges.size() - 1;
861  boundary_vertex_to_relevant_face_map.append(std::pair(second_midpoint, first_face_center));
862  }
863  else {
864  loop_edges.append(old_to_new_edges_map[edge2]);
865  }
866  }
867 
868  loop_lengths.append(loop_indices.size());
869  for (const int j : loop_indices) {
870  loops.append(j);
871  }
872  }
873  Mesh *mesh_out = BKE_mesh_new_nomain(
874  vertex_positions.size(), new_edges.size(), 0, loops.size(), loop_lengths.size());
875  transfer_attributes(attributes,
876  vertex_types,
877  keep_boundaries,
878  new_to_old_edges_map,
879  new_to_old_face_corners_map,
880  boundary_vertex_to_relevant_face_map,
881  bke::mesh_attributes(mesh_in),
882  bke::mesh_attributes_for_write(*mesh_out));
883 
884  int loop_start = 0;
885  for (const int i : IndexRange(mesh_out->totpoly)) {
886  mesh_out->mpoly[i].loopstart = loop_start;
887  mesh_out->mpoly[i].totloop = loop_lengths[i];
888  loop_start += loop_lengths[i];
889  }
890  for (const int i : IndexRange(mesh_out->totloop)) {
891  mesh_out->mloop[i].v = loops[i];
892  mesh_out->mloop[i].e = loop_edges[i];
893  }
894  for (const int i : IndexRange(mesh_out->totvert)) {
895  copy_v3_v3(mesh_out->mvert[i].co, vertex_positions[i]);
896  }
897  memcpy(mesh_out->medge, new_edges.data(), sizeof(MEdge) * new_edges.size());
898  geometry_set.replace_mesh(mesh_out);
899 }
900 
902 {
903  GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh");
904  const bool keep_boundaries = params.extract_input<bool>("Keep Boundaries");
905  geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) {
906  if (geometry_set.has_mesh()) {
908  calc_dual_mesh(geometry_set, component, keep_boundaries);
909  }
910  });
911  params.set_output("Dual Mesh", std::move(geometry_set));
912 }
913 
914 } // namespace blender::nodes::node_geo_dual_mesh_cc
915 
917 {
918  namespace file_ns = blender::nodes::node_geo_dual_mesh_cc;
919 
920  static bNodeType ntype;
924  nodeRegisterType(&ntype);
925 }
eAttrDomain
Definition: BKE_attribute.h:25
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
@ ATTR_DOMAIN_FACE
Definition: BKE_attribute.h:29
@ ATTR_DOMAIN_EDGE
Definition: BKE_attribute.h:28
@ GEO_COMPONENT_TYPE_MESH
void BKE_mesh_calc_poly_center(const struct MPoly *mpoly, const struct MLoop *loopstart, const struct MVert *mvarray, float r_cent[3])
struct Mesh * BKE_mesh_new_nomain(int verts_len, int edges_len, int tessface_len, int loops_len, int polys_len)
Definition: mesh.cc:991
#define NODE_CLASS_GEOMETRY
Definition: BKE_node.h:359
#define GEO_NODE_DUAL_MESH
Definition: BKE_node.h:1478
void nodeRegisterType(struct bNodeType *ntype)
Definition: node.cc:1357
#define BLI_assert_unreachable()
Definition: BLI_assert.h:93
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE void copy_v3_v3(float r[3], const float a[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
Definition: math_vector.c:237
#define ELEM(...)
static uint8 component(Color32 c, uint i)
Definition: ColorBlock.cpp:108
void swap(T &a, T &b)
Definition: Common.h:19
eCustomDataType
struct MEdge MEdge
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
const Mesh * get_for_read() const
const T & first() const
Definition: BLI_array.hh:269
int64_t size() const
Definition: BLI_array.hh:244
IndexRange index_range() const
Definition: BLI_array.hh:348
void reinitialize(const int64_t new_size)
Definition: BLI_array.hh:387
MutableSpan< T > typed() const
const CPPType & type() const
VArray< T > typed() const
ItemIterator items() const
Definition: BLI_map.hh:859
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr void fill(const T &value)
Definition: BLI_span.hh:527
constexpr T & last(const int64_t n=0) const
Definition: BLI_span.hh:680
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr MutableSpan take_front(const int64_t n) const
Definition: BLI_span.hh:620
int64_t size() const
Definition: BLI_vector.hh:694
void append(const T &value)
Definition: BLI_vector.hh:433
GAttributeReader lookup(const AttributeIDRef &attribute_id) const
GSpanAttributeWriter lookup_or_add_for_write_only_span(const AttributeIDRef &attribute_id, const eAttrDomain domain, const eCustomDataType data_type)
uiWidgetBaseParameters params[MAX_WIDGET_BASE_BATCH]
#define T
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
AttributeAccessor mesh_attributes(const Mesh &mesh)
eCustomDataType cpp_type_to_custom_data_type(const blender::CPPType &type)
Definition: customdata.cc:5337
MutableAttributeAccessor mesh_attributes_for_write(Mesh &mesh)
static void node_geo_exec(GeoNodeExecParams params)
static void node_declare(NodeDeclarationBuilder &b)
static bool sort_vertex_polys(const Mesh &mesh, const int vertex_index, const bool boundary_vertex, const Span< EdgeType > edge_types, MutableSpan< int > connected_polygons, MutableSpan< int > r_shared_edges, MutableSpan< int > r_sorted_corners)
static void calc_boundaries(const Mesh &mesh, MutableSpan< VertexType > r_vertex_types, MutableSpan< EdgeType > r_edge_types)
static void copy_data_based_on_new_to_old_map(Span< T > data, MutableSpan< T > r_data, const Span< int > new_to_old_map)
static void copy_data_based_on_pairs(Span< T > data, MutableSpan< T > r_data, const Span< std::pair< int, int >> new_to_old_map)
static EdgeType get_edge_type_with_added_neighbor(EdgeType old_type)
static void boundary_edges_on_poly(const MPoly &poly, const Mesh &mesh, const int vertex_index, const Span< EdgeType > edge_types, int &r_edge1, int &r_edge2)
static void create_vertex_poly_map(const Mesh &mesh, MutableSpan< Vector< int >> r_vertex_poly_indices)
static void add_edge(const Mesh &mesh, const int old_edge_i, const int v1, const int v2, Vector< int > &new_to_old_edges_map, Vector< MEdge > &new_edges, Vector< int > &loop_edges)
static void dissolve_redundant_verts(const Mesh &mesh, const Span< Vector< int >> vertex_poly_indices, MutableSpan< VertexType > vertex_types, MutableSpan< int > old_to_new_edges_map, Vector< MEdge > &new_edges, Vector< int > &new_to_old_edges_map)
static void copy_data_based_on_vertex_types(Span< T > data, MutableSpan< T > r_data, const Span< VertexType > vertex_types, const bool keep_boundaries)
static void calc_dual_mesh(GeometrySet &geometry_set, const MeshComponent &in_component, const bool keep_boundaries)
static VertexType get_vertex_type_with_added_neighbor(VertexType old_type)
static void transfer_attributes(const Map< AttributeIDRef, AttributeKind > &attributes, const Span< VertexType > vertex_types, const bool keep_boundaries, const Span< int > new_to_old_edges_map, const Span< int > new_to_old_face_corners_map, const Span< std::pair< int, int >> boundary_vertex_to_relevant_face_map, const AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes)
static void boundary_edge_on_poly(const MPoly &poly, const Mesh &mesh, const int vertex_index, const Span< EdgeType > edge_types, int &r_edge)
static bool vertex_needs_dissolving(const int vertex, const int first_poly_index, const int second_poly_index, const Span< VertexType > vertex_types, const Span< Vector< int >> vertex_poly_indices)
static MEdge new_edge(const int v1, const int v2)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
void register_node_type_geo_dual_mesh()
void geo_node_type_base(bNodeType *ntype, int type, const char *name, short nclass)
signed char int8_t
Definition: stdint.h:75
const GeometryComponent * get_component_for_read(GeometryComponentType component_type) const
void gather_attributes_for_propagation(blender::Span< GeometryComponentType > component_types, GeometryComponentType dst_component_type, bool include_instances, blender::Map< blender::bke::AttributeIDRef, blender::bke::AttributeKind > &r_attributes) const
void modify_geometry_sets(ForeachSubGeometryCallback callback)
bool has_mesh() const
unsigned int v1
unsigned int v2
unsigned int e
unsigned int v
float co[3]
struct MEdge * medge
struct MVert * mvert
int totedge
int totvert
struct MLoop * mloop
int totpoly
int totloop
struct MPoly * mpoly
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