Blender V5.3
node_geo_dual_mesh.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include <algorithm>
6
7#include "BLI_task.hh"
8
10#include "BKE_mesh.hh"
11
13#include "GEO_randomize.hh"
14
15#include "node_geometry_util.hh"
16
18
20{
21 b.use_custom_socket_order();
22 b.allow_any_socket_order();
23 b.add_input<decl::Geometry>("Mesh"_ustr)
24 .supported_type(GeometryComponent::Type::Mesh)
25 .description("Mesh to compute the dual of");
26 b.add_output<decl::Geometry>("Dual Mesh"_ustr).propagate_all_geometry().align_with_previous();
27 b.add_input<decl::Bool>("Keep Boundaries"_ustr)
28 .default_value(false)
30 "Keep non-manifold boundaries of the input mesh in place by avoiding the dual "
31 "transformation there");
32}
33
34enum class EdgeType : int8_t {
35 Loose = 0, /* No faces connected to it. */
36 Boundary = 1, /* An edge connected to exactly one face. */
37 Normal = 2, /* A normal edge (connected to two faces). */
38 NonManifold = 3, /* An edge connected to more than two faces. */
39};
40
42{
43 switch (old_type) {
44 case EdgeType::Loose:
45 return EdgeType::Boundary;
47 return EdgeType::Normal;
51 }
53 return EdgeType::Loose;
54}
55
56enum class VertexType : int8_t {
57 Loose = 0, /* Either no edges connected or only loose edges connected. */
58 Normal = 1, /* A normal vertex. */
59 Boundary = 2, /* A vertex on a boundary edge. */
60 NonManifold = 3, /* A vertex on a non-manifold edge. */
61};
62
77
98 const Span<VertexType> vertex_types,
99 const bool keep_boundaries,
100 const Span<int> new_to_old_edges_map,
101 const Span<int> new_to_old_face_corners_map,
102 const Span<std::pair<int, int>> boundary_vertex_to_relevant_face_map,
103 const AttributeFilter &attribute_filter,
104 const AttributeAccessor src_attributes,
105 MutableAttributeAccessor dst_attributes)
106{
107 /* Retrieve all attributes except for position which is handled manually.
108 * Remove anonymous attributes that don't need to be propagated. */
109 Set<StringRefNull> names = src_attributes.all_names();
110 names.remove("position");
111 names.remove(".edge_verts");
112 names.remove(".corner_vert");
113 names.remove(".corner_edge");
114 names.remove("sharp_face");
115 names.remove_if([&](const StringRef name) { return attribute_filter.allow_skip(name); });
116
117 Array<int> new_face_to_old_vert;
118 const auto ensure_vert_map = [&]() {
119 if (!new_face_to_old_vert.is_empty()) {
120 return;
121 }
122 const int src_size = src_attributes.domain_size(bke::AttrDomain::Point);
123 const int dst_size = dst_attributes.domain_size(bke::AttrDomain::Face);
124 new_face_to_old_vert.reinitialize(dst_size);
125 if (keep_boundaries) {
126 int out_i = 0;
127 for (const int i : IndexRange(src_size)) {
128 if (ELEM(vertex_types[i], VertexType::Normal, VertexType::Boundary)) {
129 new_face_to_old_vert[out_i] = i;
130 out_i++;
131 }
132 }
133 }
134 else {
135 int out_i = 0;
136 for (const int i : IndexRange(src_size)) {
137 if (vertex_types[i] == VertexType::Normal) {
138 new_face_to_old_vert[out_i] = i;
139 out_i++;
140 }
141 }
142 }
143 };
144
145 IndexMaskMemory memory;
146 IndexMask boundary_vert_mask;
147 Array<int> boundary_vert_src_face;
148 const auto ensure_face_map = [&]() {
149 if (!boundary_vert_src_face.is_empty()) {
150 return;
151 }
152 Array<int> boundary_verts(boundary_vertex_to_relevant_face_map.size());
153 for (const int i : boundary_vertex_to_relevant_face_map.index_range()) {
154 boundary_verts[i] = boundary_vertex_to_relevant_face_map[i].first;
155 }
156 boundary_vert_mask = IndexMask::from_indices(boundary_verts.as_span(), memory);
157 boundary_vert_src_face.reinitialize(boundary_vert_mask.min_array_size());
158 boundary_vert_mask.foreach_index(
159 [&](const int i, const int pos) {
160 boundary_vert_src_face[i] = boundary_vertex_to_relevant_face_map[pos].second;
161 },
163 };
164
165 for (const StringRef name : names) {
166 GAttributeReader src = src_attributes.lookup(name);
167
168 AttrDomain out_domain;
169 if (src.domain == AttrDomain::Face) {
170 out_domain = AttrDomain::Point;
171 }
172 else if (src.domain == AttrDomain::Point) {
173 out_domain = AttrDomain::Face;
174 }
175 else {
176 /* Edges and Face Corners. */
177 out_domain = src.domain;
178 }
179
181 const CommonVArrayInfo info = src.varray.common_info();
183 const GPointer value(src.varray.type(), info.data);
184 if (dst_attributes.add(name, out_domain, data_type, bke::AttributeInitValue(value))) {
185 continue;
186 }
187 }
188
190 name, out_domain, data_type);
191 if (!dst) {
192 continue;
193 }
194
195 switch (src.domain) {
196 case AttrDomain::Point:
197 ensure_vert_map();
198 bke::attribute_math::gather(*src, new_face_to_old_vert, dst.span);
199 break;
200 case AttrDomain::Edge:
201 bke::attribute_math::gather(*src, new_to_old_edges_map, dst.span);
202 break;
203 case AttrDomain::Face: {
204 const GVArraySpan src_span(*src);
205 dst.span.take_front(src_span.size()).copy_from(src_span);
206 if (keep_boundaries) {
207 ensure_face_map();
209 boundary_vert_src_face,
210 boundary_vert_mask,
211 dst.span.take_front(boundary_vert_src_face.size()));
212 }
213 break;
214 }
215 case AttrDomain::Corner:
216 bke::attribute_math::gather(*src, new_to_old_face_corners_map, dst.span);
217 break;
218 default:
220 }
221 dst.finish();
222 }
223}
224
231static void calc_boundaries(const Mesh &mesh,
232 MutableSpan<VertexType> r_vertex_types,
233 MutableSpan<EdgeType> r_edge_types)
234{
235 BLI_assert(r_vertex_types.size() == mesh.verts_num);
236 BLI_assert(r_edge_types.size() == mesh.edges_num);
237 const Span<int2> edges = mesh.edges();
238 const OffsetIndices faces = mesh.faces();
239 const Span<int> corner_edges = mesh.corner_edges();
240
241 r_vertex_types.fill(VertexType::Loose);
242 r_edge_types.fill(EdgeType::Loose);
243
244 /* Add up the number of faces connected to each edge. */
245 for (const int i : IndexRange(mesh.faces_num)) {
246 for (const int edge_i : corner_edges.slice(faces[i])) {
247 r_edge_types[edge_i] = get_edge_type_with_added_neighbor(r_edge_types[edge_i]);
248 }
249 }
250
251 /* Update vertices. */
252 for (const int i : IndexRange(mesh.edges_num)) {
253 const EdgeType edge_type = r_edge_types[i];
254 if (edge_type == EdgeType::Loose) {
255 continue;
256 }
257 const int2 &edge = edges[i];
258 if (edge_type == EdgeType::Boundary) {
259 r_vertex_types[edge[0]] = get_vertex_type_with_added_neighbor(r_vertex_types[edge[0]]);
260 r_vertex_types[edge[1]] = get_vertex_type_with_added_neighbor(r_vertex_types[edge[1]]);
261 }
262 else if (edge_type >= EdgeType::NonManifold) {
263 r_vertex_types[edge[0]] = VertexType::NonManifold;
264 r_vertex_types[edge[1]] = VertexType::NonManifold;
265 }
266 }
267
268 /* Normal verts are on a normal edge, and not on boundary edges or non-manifold edges. */
269 for (const int i : IndexRange(mesh.edges_num)) {
270 const EdgeType edge_type = r_edge_types[i];
271 if (edge_type == EdgeType::Normal) {
272 const int2 &edge = edges[i];
273 if (r_vertex_types[edge[0]] == VertexType::Loose) {
274 r_vertex_types[edge[0]] = VertexType::Normal;
275 }
276 if (r_vertex_types[edge[1]] == VertexType::Loose) {
277 r_vertex_types[edge[1]] = VertexType::Normal;
278 }
279 }
280 }
281}
282
338static bool sort_vertex_faces(const Span<int2> edges,
339 const OffsetIndices<int> faces,
340 const Span<int> corner_verts,
341 const Span<int> corner_edges,
342 const int vertex_index,
343 const bool boundary_vertex,
344 const Span<EdgeType> edge_types,
345 MutableSpan<int> connected_faces,
346 MutableSpan<int> r_shared_edges,
347 MutableSpan<int> r_sorted_corners)
348{
349 if (connected_faces.size() <= 2 && (!boundary_vertex || connected_faces.is_empty())) {
350 return true;
351 }
352
353 /* For each face store the two corners whose edge contains the vertex. */
354 Array<std::pair<int, int>, 16> face_vertex_corners(connected_faces.size());
355 for (const int i : connected_faces.index_range()) {
356 bool first_edge_done = false;
357 for (const int corner : faces[connected_faces[i]]) {
358 const int edge = corner_edges[corner];
359 if (edges[edge][0] == vertex_index || edges[edge][1] == vertex_index) {
360 if (!first_edge_done) {
361 face_vertex_corners[i].first = corner;
362 first_edge_done = true;
363 }
364 else {
365 face_vertex_corners[i].second = corner;
366 break;
367 }
368 }
369 }
370 }
371
372 int shared_edge_i = -1;
373 /* Determine first face and orientation. For now the orientation of the whole loop depends
374 * on the one face we chose as first. It's probably not worth it to check every face in
375 * the loop to determine the 'average' orientation. */
376 if (boundary_vertex) {
377 /* Our first face needs to be one which has a boundary edge. */
378 for (const int i : connected_faces.index_range()) {
379 const int corner_1 = face_vertex_corners[i].first;
380 const int corner_2 = face_vertex_corners[i].second;
381 if (edge_types[corner_edges[corner_1]] == EdgeType::Boundary &&
382 corner_verts[corner_1] == vertex_index)
383 {
384 shared_edge_i = corner_edges[corner_2];
385 r_sorted_corners[0] = face_vertex_corners[i].first;
386 std::swap(connected_faces[i], connected_faces[0]);
387 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
388 break;
389 }
390 if (edge_types[corner_edges[corner_2]] == EdgeType::Boundary &&
391 corner_verts[corner_2] == vertex_index)
392 {
393 shared_edge_i = corner_edges[corner_1];
394 r_sorted_corners[0] = face_vertex_corners[i].second;
395 std::swap(connected_faces[i], connected_faces[0]);
396 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
397 break;
398 }
399 }
400 if (shared_edge_i == -1) {
401 /* The rotation is inconsistent between the two faces on the boundary. Just choose one
402 * of the face's orientation. */
403 for (const int i : connected_faces.index_range()) {
404 const int corner_1 = face_vertex_corners[i].first;
405 const int corner_2 = face_vertex_corners[i].second;
406 if (edge_types[corner_edges[corner_1]] == EdgeType::Boundary) {
407 shared_edge_i = corner_edges[corner_2];
408 r_sorted_corners[0] = face_vertex_corners[i].first;
409 std::swap(connected_faces[i], connected_faces[0]);
410 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
411 break;
412 }
413 if (edge_types[corner_edges[corner_2]] == EdgeType::Boundary) {
414 shared_edge_i = corner_edges[corner_1];
415 r_sorted_corners[0] = face_vertex_corners[i].second;
416 std::swap(connected_faces[i], connected_faces[0]);
417 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
418 break;
419 }
420 }
421 }
422 }
423 else {
424 /* Any face can be the first. Just need to check the orientation. */
425 const int corner_1 = face_vertex_corners.first().first;
426 const int corner_2 = face_vertex_corners.first().second;
427 if (corner_verts[corner_1] == vertex_index) {
428 shared_edge_i = corner_edges[corner_2];
429 r_sorted_corners[0] = face_vertex_corners[0].first;
430 }
431 else {
432 r_sorted_corners[0] = face_vertex_corners[0].second;
433 shared_edge_i = corner_edges[corner_1];
434 }
435 }
436 BLI_assert(shared_edge_i != -1);
437
438 for (const int i : IndexRange(connected_faces.size() - 1)) {
439 r_shared_edges[i] = shared_edge_i;
440
441 /* Look at the other faces to see if it has this shared edge. */
442 int j = i + 1;
443 for (; j < connected_faces.size(); ++j) {
444 const int corner_1 = face_vertex_corners[j].first;
445 const int corner_2 = face_vertex_corners[j].second;
446
447 if (corner_edges[corner_1] == shared_edge_i) {
448 r_sorted_corners[i + 1] = face_vertex_corners[j].first;
449 shared_edge_i = corner_edges[corner_2];
450 break;
451 }
452 if (corner_edges[corner_2] == shared_edge_i) {
453 r_sorted_corners[i + 1] = face_vertex_corners[j].second;
454 shared_edge_i = corner_edges[corner_1];
455 break;
456 }
457 }
458 if (j == connected_faces.size()) {
459 /* The vertex is not manifold because the faces around the vertex don't form a loop, and
460 * hence can't be sorted. */
461 return false;
462 }
463
464 std::swap(connected_faces[i + 1], connected_faces[j]);
465 std::swap(face_vertex_corners[i + 1], face_vertex_corners[j]);
466 }
467
468 if (!boundary_vertex) {
469 /* Shared edge between first and last face. */
470 r_shared_edges.last() = shared_edge_i;
471 }
472 return true;
473}
474
478static void boundary_edge_on_face(const Span<int2> edges,
479 const Span<int> face_edges,
480 const int vertex_index,
481 const Span<EdgeType> edge_types,
482 int &r_edge)
483{
484 for (const int edge_i : face_edges) {
485 if (edge_types[edge_i] == EdgeType::Boundary) {
486 const int2 &edge = edges[edge_i];
487 if (edge[0] == vertex_index || edge[1] == vertex_index) {
488 r_edge = edge_i;
489 return;
490 }
491 }
492 }
493}
494
499static void boundary_edges_on_face(const IndexRange face,
500 const Span<int2> edges,
501 const Span<int> corner_verts,
502 const Span<int> corner_edges,
503 const int vertex_index,
504 const Span<EdgeType> edge_types,
505 int &r_edge1,
506 int &r_edge2)
507{
508 bool edge1_done = false;
509 /* This is set to true if the order in which we encounter the two edges is inconsistent with the
510 * orientation of the face. */
511 bool needs_swap = false;
512 for (const int corner : face) {
513 const int edge_i = corner_edges[corner];
514 if (edge_types[edge_i] == EdgeType::Boundary) {
515 const int2 &edge = edges[edge_i];
516 if (edge[0] == vertex_index || edge[1] == vertex_index) {
517 if (edge1_done) {
518 if (needs_swap) {
519 r_edge2 = r_edge1;
520 r_edge1 = edge_i;
521 }
522 else {
523 r_edge2 = edge_i;
524 }
525 return;
526 }
527 r_edge1 = edge_i;
528 edge1_done = true;
529 if (corner_verts[corner] == vertex_index) {
530 needs_swap = true;
531 }
532 }
533 }
534 }
535}
536
537static void add_edge(const int old_edge_i,
538 const int v1,
539 const int v2,
540 Vector<int> &new_to_old_edges_map,
541 Vector<int2> &new_edges,
542 Vector<int> &corner_edges)
543{
544 const int new_edge_i = new_edges.size();
545 new_to_old_edges_map.append(old_edge_i);
546 new_edges.append({v1, v2});
547 corner_edges.append(new_edge_i);
548}
549
550/* Returns true if the vertex is connected only to the two faces and is not on the boundary. */
551static bool vertex_needs_dissolving(const int vertex,
552 const int first_face_index,
553 const int second_face_index,
554 const Span<VertexType> vertex_types,
555 const GroupedSpan<int> vert_to_face_map)
556{
557 /* Order is guaranteed to be the same because 2face verts that are not on the boundary are
558 * ignored in `sort_vertex_faces`. */
559 return (vertex_types[vertex] != VertexType::Boundary && vert_to_face_map[vertex].size() == 2 &&
560 vert_to_face_map[vertex][0] == first_face_index &&
561 vert_to_face_map[vertex][1] == second_face_index);
562}
563
571static void dissolve_redundant_verts(const Span<int2> edges,
572 const OffsetIndices<int> faces,
573 const Span<int> corner_edges,
574 const GroupedSpan<int> vert_to_face_map,
575 MutableSpan<VertexType> vertex_types,
576 MutableSpan<int> old_to_new_edges_map,
577 Vector<int2> &new_edges,
578 Vector<int> &new_to_old_edges_map)
579{
580 const int vertex_num = vertex_types.size();
581 for (const int vert_i : IndexRange(vertex_num)) {
582 if (vert_to_face_map[vert_i].size() != 2 || vertex_types[vert_i] != VertexType::Normal) {
583 continue;
584 }
585 const int first_face_index = vert_to_face_map[vert_i][0];
586 const int second_face_index = vert_to_face_map[vert_i][1];
587 const int new_edge_index = new_edges.size();
588 bool edge_created = false;
589 for (const int edge_i : corner_edges.slice(faces[first_face_index])) {
590 const int2 &edge = edges[edge_i];
591 bool mark_edge = false;
593 edge[0], first_face_index, second_face_index, vertex_types, vert_to_face_map))
594 {
595 /* This vertex is now 'removed' and should be ignored elsewhere. */
596 vertex_types[edge[0]] = VertexType::Loose;
597 mark_edge = true;
598 }
600 edge[1], first_face_index, second_face_index, vertex_types, vert_to_face_map))
601 {
602 /* This vertex is now 'removed' and should be ignored elsewhere. */
603 vertex_types[edge[1]] = VertexType::Loose;
604 mark_edge = true;
605 }
606 if (mark_edge) {
607 if (!edge_created) {
608 /* The vertex indices in the dual mesh are the face indices of the input mesh. */
609 new_to_old_edges_map.append(edge_i);
610 new_edges.append({first_face_index, second_face_index});
611 edge_created = true;
612 }
613 old_to_new_edges_map[edge_i] = new_edge_index;
614 }
615 }
616 }
617}
618
633static Mesh *calc_dual_mesh(const Mesh &src_mesh,
634 const bool keep_boundaries,
635 const AttributeFilter &attribute_filter)
636{
637 const Span<float3> src_positions = src_mesh.vert_positions();
638 const Span<int2> src_edges = src_mesh.edges();
639 const OffsetIndices src_faces = src_mesh.faces();
640 const Span<int> src_corner_verts = src_mesh.corner_verts();
641 const Span<int> src_corner_edges = src_mesh.corner_edges();
642
643 Array<VertexType> vertex_types(src_mesh.verts_num);
644 Array<EdgeType> edge_types(src_mesh.edges_num);
645 calc_boundaries(src_mesh, vertex_types, edge_types);
646 /* Stores the indices of the faces connected to the vertex. Because the faces are looped
647 * over in order of their indices, the face's indices will be sorted in ascending order.
648 * (This can change once they are sorted using `sort_vertex_faces`). */
649 Array<int> vert_to_face_indices = src_mesh.vert_to_face_map().data;
650 const OffsetIndices<int> vert_to_face_offsets = src_mesh.vert_to_face_map().offsets;
651
652 Array<Array<int>> vertex_shared_edges(src_mesh.verts_num);
653 Array<Array<int>> vertex_corners(src_mesh.verts_num);
654 threading::parallel_for(src_positions.index_range(), 512, [&](IndexRange range) {
655 for (const int i : range) {
656 if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
657 (!keep_boundaries && vertex_types[i] == VertexType::Boundary))
658 {
659 /* Bad vertex that we can't work with. */
660 continue;
661 }
662 MutableSpan<int> corner_indices = vert_to_face_indices.as_mutable_span().slice(
663 vert_to_face_offsets[i]);
664 Array<int> sorted_corners(corner_indices.size());
665 bool vertex_ok = true;
666 if (vertex_types[i] == VertexType::Normal) {
667 Array<int> shared_edges(corner_indices.size());
668 vertex_ok = sort_vertex_faces(src_edges,
669 src_faces,
670 src_corner_verts,
671 src_corner_edges,
672 i,
673 false,
674 edge_types,
675 corner_indices,
676 shared_edges,
677 sorted_corners);
678 vertex_shared_edges[i] = std::move(shared_edges);
679 }
680 else {
681 Array<int> shared_edges(corner_indices.size() - 1);
682 vertex_ok = sort_vertex_faces(src_edges,
683 src_faces,
684 src_corner_verts,
685 src_corner_edges,
686 i,
687 true,
688 edge_types,
689 corner_indices,
690 shared_edges,
691 sorted_corners);
692 vertex_shared_edges[i] = std::move(shared_edges);
693 }
694 if (!vertex_ok) {
695 /* The sorting failed which means that the vertex is non-manifold and should be ignored
696 * further on. */
697 vertex_types[i] = VertexType::NonManifold;
698 continue;
699 }
700 vertex_corners[i] = std::move(sorted_corners);
701 }
702 });
703
704 const GroupedSpan<int> vert_to_face_map(vert_to_face_offsets, vert_to_face_indices);
705
706 Vector<float3> vert_positions(src_mesh.faces_num);
707 for (const int i : src_faces.index_range()) {
708 const IndexRange face = src_faces[i];
709 vert_positions[i] = bke::mesh::face_center_calc(src_positions, src_corner_verts.slice(face));
710 }
711
712 Array<int> boundary_edge_midpoint_index;
713 if (keep_boundaries) {
714 /* Only initialize when we actually need it. */
715 boundary_edge_midpoint_index.reinitialize(src_mesh.edges_num);
716 /* We need to add vertices at the centers of boundary edges. */
717 for (const int i : IndexRange(src_mesh.edges_num)) {
718 if (edge_types[i] == EdgeType::Boundary) {
719 const int2 &edge = src_edges[i];
720 const float3 mid = math::midpoint(src_positions[edge[0]], src_positions[edge[1]]);
721 boundary_edge_midpoint_index[i] = vert_positions.size();
722 vert_positions.append(mid);
723 }
724 }
725 }
726
727 Vector<int> face_sizes;
728 Vector<int> corner_verts;
729 Vector<int> corner_edges;
730 Vector<int2> new_edges;
731 /* These are used to transfer attributes. */
732 Vector<int> new_to_old_face_corners_map;
733 Vector<int> new_to_old_edges_map;
734 /* Stores the index of the vertex in the dual and the face it should get the attribute from. */
735 Vector<std::pair<int, int>> boundary_vertex_to_relevant_face_map;
736 /* Since each edge in the dual (except the ones created with keep boundaries) comes from
737 * exactly one edge in the original, we can use this array to keep track of whether it still
738 * needs to be created or not. If it's not -1 it gives the index in `new_edges` of the dual
739 * edge. The edges coming from preserving the boundaries only get added once anyway, so we
740 * don't need a hash-map for that. */
741 Array<int> old_to_new_edges_map(src_mesh.edges_num);
742 old_to_new_edges_map.fill(-1);
743
744 /* This is necessary to prevent duplicate edges from being created, but will likely not do
745 * anything for most meshes. */
746 dissolve_redundant_verts(src_edges,
747 src_faces,
748 src_corner_edges,
749 vert_to_face_map,
750 vertex_types,
751 old_to_new_edges_map,
752 new_edges,
753 new_to_old_edges_map);
754
755 for (const int i : IndexRange(src_mesh.verts_num)) {
756 if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
757 (!keep_boundaries && vertex_types[i] == VertexType::Boundary))
758 {
759 /* Bad vertex that we can't work with. */
760 continue;
761 }
762
763 Vector<int> corner_indices = vert_to_face_map[i];
764 Span<int> shared_edges = vertex_shared_edges[i];
765 Span<int> sorted_corners = vertex_corners[i];
766 if (vertex_types[i] == VertexType::Normal) {
767 if (corner_indices.size() <= 2) {
768 /* We can't make a face from 2 vertices. */
769 continue;
770 }
771
772 /* Add edges in the loop. */
773 for (const int i : shared_edges.index_range()) {
774 const int old_edge_i = shared_edges[i];
775 if (old_to_new_edges_map[old_edge_i] == -1) {
776 /* This edge has not been created yet. */
777 new_to_old_edges_map.append(old_edge_i);
778 old_to_new_edges_map[old_edge_i] = new_edges.size();
779 new_edges.append({corner_indices[i], corner_indices[(i + 1) % corner_indices.size()]});
780 }
781 corner_edges.append(old_to_new_edges_map[old_edge_i]);
782 }
783
784 new_to_old_face_corners_map.extend(sorted_corners);
785 }
786 else {
810
811 /* Add the edges in between the faces. */
812 for (const int i : shared_edges.index_range()) {
813 const int old_edge_i = shared_edges[i];
814 if (old_to_new_edges_map[old_edge_i] == -1) {
815 /* This edge has not been created yet. */
816 new_to_old_edges_map.append(old_edge_i);
817 old_to_new_edges_map[old_edge_i] = new_edges.size();
818 new_edges.append({corner_indices[i], corner_indices[i + 1]});
819 }
820 corner_edges.append(old_to_new_edges_map[old_edge_i]);
821 }
822
823 new_to_old_face_corners_map.extend(sorted_corners);
824
825 /* Add the vertex and the midpoints of the two boundary edges to the loop. */
826
827 /* Get the boundary edges. */
828 int edge1;
829 int edge2;
830 if (corner_indices.size() >= 2) {
831 /* The first boundary edge is at the end of the chain of faces. */
832 boundary_edge_on_face(src_edges,
833 src_corner_edges.slice(src_faces[corner_indices.last()]),
834 i,
835 edge_types,
836 edge1);
837 boundary_edge_on_face(src_edges,
838 src_corner_edges.slice(src_faces[corner_indices.first()]),
839 i,
840 edge_types,
841 edge2);
842 }
843 else {
844 /* If there is only one face both edges are in that face. */
845 boundary_edges_on_face(src_faces[corner_indices[0]],
846 src_edges,
847 src_corner_verts,
848 src_corner_edges,
849 i,
850 edge_types,
851 edge1,
852 edge2);
853 }
854
855 const int last_face_center = corner_indices.last();
856 corner_indices.append(boundary_edge_midpoint_index[edge1]);
857 new_to_old_face_corners_map.append(sorted_corners.last());
858 const int first_midpoint = corner_indices.last();
859 if (old_to_new_edges_map[edge1] == -1) {
860 add_edge(edge1,
861 last_face_center,
862 first_midpoint,
863 new_to_old_edges_map,
864 new_edges,
865 corner_edges);
866 old_to_new_edges_map[edge1] = new_edges.size() - 1;
867 boundary_vertex_to_relevant_face_map.append(std::pair(first_midpoint, last_face_center));
868 }
869 else {
870 corner_edges.append(old_to_new_edges_map[edge1]);
871 }
872 corner_indices.append(vert_positions.size());
873 /* This is sort of arbitrary, but interpolating would be a lot harder to do. */
874 new_to_old_face_corners_map.append(sorted_corners.first());
875 boundary_vertex_to_relevant_face_map.append(
876 std::pair(corner_indices.last(), last_face_center));
877 vert_positions.append(src_positions[i]);
878 const int boundary_vertex = corner_indices.last();
879 add_edge(
880 edge1, first_midpoint, boundary_vertex, new_to_old_edges_map, new_edges, corner_edges);
881
882 corner_indices.append(boundary_edge_midpoint_index[edge2]);
883 new_to_old_face_corners_map.append(sorted_corners.first());
884 const int second_midpoint = corner_indices.last();
885 add_edge(
886 edge2, boundary_vertex, second_midpoint, new_to_old_edges_map, new_edges, corner_edges);
887
888 if (old_to_new_edges_map[edge2] == -1) {
889 const int first_face_center = corner_indices.first();
890 add_edge(edge2,
891 second_midpoint,
892 first_face_center,
893 new_to_old_edges_map,
894 new_edges,
895 corner_edges);
896 old_to_new_edges_map[edge2] = new_edges.size() - 1;
897 boundary_vertex_to_relevant_face_map.append(std::pair(second_midpoint, first_face_center));
898 }
899 else {
900 corner_edges.append(old_to_new_edges_map[edge2]);
901 }
902 }
903
904 face_sizes.append(corner_indices.size());
905 corner_verts.extend(corner_indices);
906 }
907 Mesh *mesh_out = BKE_mesh_new_nomain(
908 vert_positions.size(), new_edges.size(), face_sizes.size(), corner_verts.size());
909 bke::mesh_smooth_set(*mesh_out, false);
910
911 std::ranges::sort(boundary_vertex_to_relevant_face_map,
912 [](const auto &a, const auto &b) { return a.first < b.first; });
913
914 transfer_attributes(vertex_types,
915 keep_boundaries,
916 new_to_old_edges_map,
917 new_to_old_face_corners_map,
918 boundary_vertex_to_relevant_face_map,
919 attribute_filter,
920 src_mesh.attributes(),
921 mesh_out->attributes_for_write());
922
923 mesh_out->vert_positions_for_write().copy_from(vert_positions);
924 mesh_out->edges_for_write().copy_from(new_edges);
925
926 if (mesh_out->faces_num > 0) {
927 MutableSpan<int> dst_face_offsets = mesh_out->face_offsets_for_write();
928 dst_face_offsets.drop_back(1).copy_from(face_sizes);
930 }
931 mesh_out->corner_verts_for_write().copy_from(corner_verts);
932 mesh_out->corner_edges_for_write().copy_from(corner_edges);
933
934 return mesh_out;
935}
936
938{
939 GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh"_ustr);
940 const bool keep_boundaries = params.extract_input<bool>("Keep Boundaries"_ustr);
941 geometry::foreach_real_geometry(geometry_set, [&](GeometrySet &geometry_set) {
942 if (const Mesh *mesh = geometry_set.get_mesh()) {
943 Mesh *new_mesh = calc_dual_mesh(
944 *mesh, keep_boundaries, params.get_attribute_filter("Dual Mesh"_ustr));
946 geometry_set.replace_mesh(new_mesh);
947 }
948 });
949 params.set_output("Dual Mesh"_ustr, std::move(geometry_set));
950}
951
952static void node_register()
953{
954 static bke::bNodeType ntype;
955 geo_node_type_base(&ntype, "GeometryNodeDualMesh"_ustr, GEO_NODE_DUAL_MESH);
956 ntype.ui_name = "Dual Mesh";
957 ntype.ui_description = "Convert Faces into vertices and vertices into faces";
958 ntype.enum_name_legacy = "DUAL_MESH";
960 ntype.declare = node_declare;
963}
964NOD_REGISTER_NODE(node_register)
965
966} // namespace blender::nodes::node_geo_dual_mesh_cc
#define NODE_CLASS_GEOMETRY
Definition BKE_node.hh:492
#define GEO_NODE_DUAL_MESH
#define NOD_REGISTER_NODE(REGISTER_FUNC)
#define BLI_assert_unreachable()
#define ELEM(...)
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr const T & last(const int64_t n=0) const
Definition BLI_span.hh:329
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
int64_t size() const
Definition BLI_array.hh:267
Span< T > as_span() const
Definition BLI_array.hh:254
const T & first() const
Definition BLI_array.hh:292
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
bool is_empty() const
Definition BLI_array.hh:275
void copy_from(GSpan values)
GMutableSpan take_front(const int64_t n) const
int64_t size() const
CommonVArrayInfo common_info() const
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr bool is_empty() const
Definition BLI_span.hh:515
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
int64_t remove_if(Predicate &&predicate)
Definition BLI_set.hh:534
bool remove(const Key &key)
Definition BLI_set.hh:404
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
int64_t size() const
void append(const T &value)
Set< StringRefNull > all_names() const
GAttributeReader lookup(const StringRef name) const
int domain_size(const AttrDomain domain) const
bool add(const StringRef name, const AttrDomain domain, const AttrType data_type, const AttributeInit &initializer)
GSpanAttributeWriter lookup_or_add_for_write_only_span(StringRef name, AttrDomain domain, AttrType data_type)
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
NodeAttributeFilter get_attribute_filter(const UString output_identifier) const
T extract_input(const UString identifier)
void set_output(const UString identifier, T &&value)
#define vertex
void gather(GSpan src, Span< int > map, GMutableSpan dst)
float3 face_center_calc(Span< float3 > vert_positions, Span< int > face_verts)
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
void mesh_smooth_set(Mesh &mesh, bool use_smooth, bool keep_sharp_edges=false)
AttrType cpp_type_to_attribute_type(const CPPType &type)
constexpr ParallelGrainSize grain_size(int grain_size)
void foreach_real_geometry(bke::GeometrySet &geometry, FunctionRef< void(bke::GeometrySet &geometry_set)> fn)
void debug_randomize_mesh_order(Mesh *mesh)
Definition randomize.cc:305
T midpoint(const T &a, const T &b)
static void node_geo_exec(GeoNodeExecParams params)
static void dissolve_redundant_verts(const Span< int2 > edges, const OffsetIndices< int > faces, const Span< int > corner_edges, const GroupedSpan< int > vert_to_face_map, MutableSpan< VertexType > vertex_types, MutableSpan< int > old_to_new_edges_map, Vector< int2 > &new_edges, Vector< int > &new_to_old_edges_map)
static void node_declare(NodeDeclarationBuilder &b)
static void calc_boundaries(const Mesh &mesh, MutableSpan< VertexType > r_vertex_types, MutableSpan< EdgeType > r_edge_types)
static EdgeType get_edge_type_with_added_neighbor(EdgeType old_type)
static void boundary_edge_on_face(const Span< int2 > edges, const Span< int > face_edges, const int vertex_index, const Span< EdgeType > edge_types, int &r_edge)
static void boundary_edges_on_face(const IndexRange face, const Span< int2 > edges, const Span< int > corner_verts, const Span< int > corner_edges, const int vertex_index, const Span< EdgeType > edge_types, int &r_edge1, int &r_edge2)
static void transfer_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 AttributeFilter &attribute_filter, const AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes)
static bool sort_vertex_faces(const Span< int2 > edges, const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< int > corner_edges, const int vertex_index, const bool boundary_vertex, const Span< EdgeType > edge_types, MutableSpan< int > connected_faces, MutableSpan< int > r_shared_edges, MutableSpan< int > r_sorted_corners)
static bool vertex_needs_dissolving(const int vertex, const int first_face_index, const int second_face_index, const Span< VertexType > vertex_types, const GroupedSpan< int > vert_to_face_map)
static void add_edge(const int old_edge_i, const int v1, const int v2, Vector< int > &new_to_old_edges_map, Vector< int2 > &new_edges, Vector< int > &corner_edges)
static Mesh * calc_dual_mesh(const Mesh &src_mesh, const bool keep_boundaries, const AttributeFilter &attribute_filter)
static VertexType get_vertex_type_with_added_neighbor(VertexType old_type)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
VecBase< int32_t, 2 > int2
Mesh * BKE_mesh_new_nomain(int verts_num, int edges_num, int faces_num, int corners_num)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
VecBase< float, 3 > float3
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
signed char int8_t
Definition BKE_text.h:76
bool allow_skip(const StringRef name) const
const Mesh * get_mesh() const
void replace_mesh(Mesh *mesh, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
Defines a node type.
Definition BKE_node.hh:265
std::string ui_description
Definition BKE_node.hh:271
NodeGeometryExecFunction geometry_node_execute
Definition BKE_node.hh:385
const char * enum_name_legacy
Definition BKE_node.hh:274
NodeDeclareFunction declare
Definition BKE_node.hh:393