Blender V5.3
mesh_merge_verts.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
8
9// #define USE_WELD_DEBUG
10// #define USE_WELD_DEBUG_TIME
11
12#include "BKE_attribute_math.hh"
13#include "BLI_array.hh"
14#include "BLI_array_utils.hh"
15#include "BLI_index_mask.hh"
16#include "BLI_kdtree_new.hh"
17#include "BLI_listbase.hh"
18#include "BLI_math_vector_c.hh"
19#include "BLI_offset_indices.hh"
20#include "BLI_ordered_edge.hh"
21#include "BLI_task.hh"
22#include "BLI_vector.hh"
23
24#include "BKE_attribute.hh"
26#include "BKE_customdata.hh"
27#include "BKE_deform.hh"
28#include "BKE_mesh.hh"
29#include "DNA_meshdata_types.h"
30
31#include "DNA_object_types.h"
33#include "GEO_randomize.hh"
34
35#ifdef USE_WELD_DEBUG_TIME
36# include "BLI_timeit.hh"
37
38# if WIN32 and NDEBUG
39# pragma optimize("t", on)
40# endif
41#endif
42
43namespace blender::geometry {
44
45/* Indicates when the element was not computed. */
46#define OUT_OF_CONTEXT int(-1)
47/* Indicates if the edge or face will be collapsed. */
48#define ELEM_COLLAPSED int(-2)
49/* indicates whether an edge or vertex in groups_map will be merged. */
50#define ELEM_MERGED int(-2)
51/* Indicates that a face is a duplicate of another face after merging. */
52#define ELEM_DUPLICATE int(-3)
53
54struct WeldFace {
60 /* Indices in to the source Mesh. */
67};
68
71 int faces = 0;
72 int corners = 0;
73
76 {
77 return {a.faces + b.faces, a.corners + b.corners};
78 }
79};
80
81struct WeldMesh {
82 /* Group of edges to be merged. */
85 /* Vertices that merge into another vertex, and the vertices they merge into. */
87
88 /* References all faces that will be affected. */
91
99
101
105 int removed_faces_num; /* Including the new faces. */
106
107#ifdef USE_WELD_DEBUG
108 Span<int> corner_verts;
109 Span<int> corner_edges;
110 OffsetIndices<int> faces;
111#endif
112};
113
114template<typename Fn>
115static void foreach_weld_face_corner(const WeldFace &weld_face,
116 const Span<int> corner_next,
117 const Fn &fn)
118{
119 BLI_assert(weld_face.face_dst == OUT_OF_CONTEXT);
120 int corner = weld_face.corner_start;
121 do {
122 fn(corner);
123 corner = corner_next[corner];
124 } while (corner != weld_face.corner_start);
125}
126
127/* -------------------------------------------------------------------- */
130
131#ifdef USE_WELD_DEBUG
132static void weld_assert_removed_edges_num(Span<int> edge_src_to_target,
133 const int expected_removed_num)
134{
135 int kills = 0;
136 for (const int edge_src : edge_src_to_target.index_range()) {
137 if (edge_src_to_target[edge_src] != edge_src) {
138 kills++;
139 }
140 }
141 BLI_assert(kills == expected_removed_num);
142}
143
144static void weld_assert_removed_faces_and_corners_num(const WeldMesh &weld_mesh,
145 const int expected_removed_faces_num,
146 const int expected_removed_corners_num)
147{
148 const OffsetIndices<int> faces = weld_mesh.faces;
149 int removed_faces = 0;
150 int remaining_corners = 0;
151 for (const int i : faces.index_range()) {
152 if (weld_mesh.face_to_weld_face[i] == OUT_OF_CONTEXT) {
153 remaining_corners += faces[i].size();
154 }
155 }
156 for (const WeldFace &weld_face : weld_mesh.weld_faces) {
157 if (weld_face.face_dst != OUT_OF_CONTEXT) {
158 removed_faces++;
159 continue;
160 }
162 weld_face, weld_mesh.corner_next, [&](const int /*corner*/) { remaining_corners++; });
163 }
164 BLI_assert(removed_faces == expected_removed_faces_num);
165 BLI_assert(weld_mesh.corner_verts.size() - remaining_corners == expected_removed_corners_num);
166}
167
168static void weld_assert_face_no_vert_repetition(const WeldFace &weld_face,
169 const WeldMesh &weld_mesh)
170{
171 if (weld_face.face_dst != OUT_OF_CONTEXT) {
172 return;
173 }
174 Vector<int> verts;
175 foreach_weld_face_corner(weld_face, weld_mesh.corner_next, [&](const int corner) {
176 verts.append(weld_mesh.vert_src_to_target[weld_mesh.corner_verts[corner]]);
177 });
178 BLI_assert(verts.size() == weld_face.corners_num);
179 for (const int i : verts.index_range()) {
180 for (const int j : verts.index_range().drop_front(i + 1)) {
181 BLI_assert(verts[i] != verts[j]);
182 }
183 }
184}
185
186#endif /* USE_WELD_DEBUG */
187
189
190/* -------------------------------------------------------------------- */
193
198static Array<bool> find_affected_verts(const Span<int> vert_src_to_target)
199{
200 Array<bool> affected(vert_src_to_target.size(), false);
201 threading::parallel_for(vert_src_to_target.index_range(), 4096, [&](const IndexRange range) {
202 for (const int vert : range) {
203 const int vert_target = vert_src_to_target[vert];
204 if (vert_target != vert) {
205 BLI_assert(vert_src_to_target[vert_target] == vert_target);
206 affected[vert] = true;
207 /* All threads will store the same "true" value. */
208 affected[vert_target] = true;
209 }
210 }
211 });
212 return affected;
213}
214
216
217/* -------------------------------------------------------------------- */
220
230 const Span<int> vert_src_to_target,
231 const Span<bool> vert_affected,
232 IndexMaskMemory &memory,
233 MutableSpan<int> r_edge_src_to_target,
234 int *r_collapsed_edges_num)
235{
236 const IndexMask affected_edges = IndexMask::from_predicate(
237 edges.index_range(),
238 memory,
239 [&](const int edge) {
240 return vert_affected[edges[edge][0]] || vert_affected[edges[edge][1]];
241 },
243 const IndexMask weld_edges = IndexMask::from_predicate(
244 affected_edges,
245 memory,
246 [&](const int edge) {
247 return vert_src_to_target[edges[edge][0]] != vert_src_to_target[edges[edge][1]];
248 },
250 const IndexMask collapsed_edges = IndexMask::from_difference(affected_edges, weld_edges, memory);
251
252 array_utils::fill_index_range<int>(edges.index_range(), r_edge_src_to_target);
253 index_mask::masked_fill(r_edge_src_to_target, ELEM_COLLAPSED, collapsed_edges);
254 *r_collapsed_edges_num = collapsed_edges.size();
255 return weld_edges;
256}
257
264static int find_duplicate_edges(const Span<int2> edges,
265 const Span<int> vert_src_to_target,
266 const IndexMask &weld_edges,
267 const int verts_num,
268 MutableSpan<int> r_edge_src_to_target)
269{
270 if (weld_edges.is_empty()) {
271 return 0;
272 }
273
274 Array<int> edge_indices(weld_edges.size());
275 Array<int> low_verts(weld_edges.size());
276 Array<int> high_verts(weld_edges.size());
277 weld_edges.foreach_index(
278 [&](const int edge, const int pos) {
279 const OrderedEdge verts(vert_src_to_target[edges[edge][0]],
280 vert_src_to_target[edges[edge][1]]);
281 edge_indices[pos] = edge;
282 low_verts[pos] = verts.v_low;
283 high_verts[pos] = verts.v_high;
284 },
286
287 /* Duplicate edges share their lower vertex, so only edges in the same group can be duplicates.
288 */
289 Array<int> offset_data;
290 Array<int> index_data;
292 low_verts, verts_num, offset_data, index_data)
293 .offsets;
294
296 edges_by_low_vert.index_range(),
297 1024,
298 0,
299 [&](const IndexRange range, int duplicates_num) {
300 for (const int vert : range) {
301 MutableSpan<int> group = index_data.as_mutable_span().slice(edges_by_low_vert[vert]);
302 if (group.size() < 2) {
303 continue;
304 }
305 /* After sorting by the higher vertex, duplicates are next to each other, and the first
306 * of each group of duplicates has the lowest index. */
307 std::ranges::sort(group, [&](const int a, const int b) {
308 return std::pair(high_verts[a], a) < std::pair(high_verts[b], b);
309 });
310 int first = group[0];
311 for (const int weld_edge : group.drop_front(1)) {
312 if (high_verts[weld_edge] != high_verts[first]) {
313 first = weld_edge;
314 continue;
315 }
316 r_edge_src_to_target[edge_indices[weld_edge]] = edge_indices[first];
317 duplicates_num++;
318 }
319 }
320 return duplicates_num;
321 },
322 std::plus<>());
323}
324
326
327/* -------------------------------------------------------------------- */
330
337 const Span<int> corner_verts,
338 WeldMesh *r_weld_mesh)
339{
340 const Span<bool> vert_affected = r_weld_mesh->vert_affected;
341
342 IndexMaskMemory memory;
343 const IndexMask affected_faces = IndexMask::from_predicate(
344 faces.index_range(),
345 memory,
346 [&](const int face) {
347 return std::ranges::any_of(corner_verts.slice(faces[face]),
348 [&](const int vert) { return vert_affected[vert]; });
349 },
351
352 /* Estimate the maximum number of new faces created by splitting faces that contain the same
353 * vertex multiple times after merging. We could be smarter here and actually count how many new
354 * faces will be created. But counting this can be inefficient as it depends on the number of
355 * non-consecutive self face merges. */
356 const int maybe_new_faces_num = threading::parallel_reduce(
357 affected_faces.index_range(),
358 1024,
359 0,
360 [&](const IndexRange range, int maybe_new_faces_num) {
361 affected_faces.slice(range).foreach_index([&](const int face_index) {
362 const IndexRange face = faces[face_index];
363 if (face.size() <= 5) {
364 return;
365 }
366 /* Corners are affected by the merge when their vertex or the next vertex merges. */
367 int corner_ctx_num = 0;
368 for (const int corner : face) {
369 const int corner_next = bke::mesh::face_corner_next(face, corner);
370 if (vert_affected[corner_verts[corner]] || vert_affected[corner_verts[corner_next]]) {
371 corner_ctx_num++;
372 }
373 }
374 if (corner_ctx_num > 1) {
375 maybe_new_faces_num += std::min(int(face.size() / 3), corner_ctx_num) - 1;
376 }
377 });
378 return maybe_new_faces_num;
379 },
380 std::plus<>());
381
382 Array<int> corner_next(corner_verts.size());
383 Array<int> face_to_weld_face(faces.size());
384 Vector<WeldFace> weld_faces;
385 weld_faces.reserve(affected_faces.size() + maybe_new_faces_num);
386 weld_faces.resize(affected_faces.size());
387
388 affected_faces.foreach_index(
389 [&](const int face_index, const int weld_face_index) {
390 const IndexRange face = faces[face_index];
391 for (const int corner : face.drop_back(1)) {
392 corner_next[corner] = corner + 1;
393 }
394 corner_next[face.last()] = face.first();
395
396 WeldFace &weld_face = weld_faces[weld_face_index];
397 weld_face.face_dst = OUT_OF_CONTEXT;
398 weld_face.face_src = face_index;
399 weld_face.corner_start = face.first();
400 weld_face.corner_end = face.last();
401 weld_face.corners_num = face.size();
402 face_to_weld_face[face_index] = weld_face_index;
403 },
404 exec_mode::grain_size(1024));
405 index_mask::masked_fill(face_to_weld_face.as_mutable_span(),
407 affected_faces.complement(faces.index_range(), memory));
408
409 r_weld_mesh->weld_faces = std::move(weld_faces);
410 r_weld_mesh->new_faces_num = 0;
411 r_weld_mesh->corner_next = std::move(corner_next);
412 r_weld_mesh->face_to_weld_face = std::move(face_to_weld_face);
413}
414
416static void weld_face_split_recursive(int face_size,
417 const Span<int> corner_verts,
418 WeldFace *r_wp,
419 WeldMesh *r_weld_mesh,
420 RemovedFacesAndCorners &r_removed)
421{
422 if (face_size < 3) {
423 return;
424 }
425
426 const Span<int> vert_src_to_target = r_weld_mesh->vert_src_to_target;
427 const Span<bool> vert_affected = r_weld_mesh->vert_affected;
428 MutableSpan<int> corner_next = r_weld_mesh->corner_next;
429
430 int removed_corners_num = 0;
431
432 int corner_end = r_wp->corner_end;
433 int corner_a_prev = corner_end;
434 int corner_a = r_wp->corner_start;
435 do {
436 const int vert_a = vert_src_to_target[corner_verts[corner_a]];
437 if (!vert_affected[vert_a]) {
438 /* Only test vertices that will be merged. */
439 corner_a_prev = corner_a;
440 corner_a = corner_next[corner_a];
441 continue;
442 }
443
444 int dist_a = 1;
445 int lb_prev = corner_a;
446 int corner_b = corner_next[corner_a];
447 do {
448 const int vert_b = vert_src_to_target[corner_verts[corner_b]];
449 if (vert_a != vert_b) {
450 dist_a++;
451 lb_prev = corner_b;
452 corner_b = corner_next[corner_b];
453 continue;
454 }
455
456 int dist_b = face_size - dist_a;
457
458 BLI_assert(dist_a != 0 && dist_b != 0);
459 if (dist_a == 1 || dist_b == 1) {
460 BLI_assert(dist_a != dist_b);
461 }
462 else if (dist_a == 2 && dist_b == 2) {
463 /* All corners are "collapsed". */
464 removed_corners_num += 4;
465 dist_b = 0;
466 r_wp->face_dst = ELEM_COLLAPSED;
467 r_removed.faces += 1;
468 r_removed.corners += removed_corners_num;
469 /* Since all the corners are collapsed, avoid iterating through them.
470 * This may result in wrong removed_faces_num counts. */
471 return;
472 }
473 else {
474 corner_next[corner_a_prev] = corner_b;
475 corner_next[lb_prev] = corner_a;
476 if (r_wp->corner_start == corner_a) {
477 r_wp->corner_start = corner_b;
478 }
479
480 if (dist_a == 2) {
481 removed_corners_num += 2;
482 }
483 else if (dist_b == 2) {
484 removed_corners_num += 2;
485
486 r_wp->corner_start = corner_a;
487 r_wp->corner_end = corner_end = lb_prev;
488
489 face_size = dist_a;
490 break;
491 }
492 else {
493 r_weld_mesh->weld_faces.increase_size_by_unchecked(1);
494 r_weld_mesh->new_faces_num++;
495
496 WeldFace *new_test = &r_weld_mesh->weld_faces.last();
497 new_test->face_dst = OUT_OF_CONTEXT;
498 new_test->face_src = r_wp->face_src;
499 new_test->corner_start = corner_a;
500 new_test->corner_end = lb_prev;
501 new_test->corners_num = dist_a;
502 weld_face_split_recursive(dist_a, corner_verts, new_test, r_weld_mesh, r_removed);
503 }
504
505 corner_a = corner_b;
506 face_size = dist_b;
507
508 dist_a = 1;
509 }
510
511 lb_prev = corner_b;
512 corner_b = corner_next[corner_b];
513 } while (lb_prev != corner_end);
514
515 corner_a_prev = corner_a;
516 if (corner_a == corner_end) {
517 /* No need to start again. */
518 break;
519 }
520 corner_a = corner_next[corner_a];
521 } while (corner_a != corner_end);
522
523 r_removed.corners += removed_corners_num;
524 r_wp->corners_num = face_size;
525#ifdef USE_WELD_DEBUG
526 weld_assert_face_no_vert_repetition(*r_wp, *r_weld_mesh);
527#endif
528}
529
534static int collapse_weld_face(const Span<int> corner_edges,
535 const Span<int> edge_src_to_target,
536 WeldFace &weld_face,
537 MutableSpan<int> corner_next,
538 RemovedFacesAndCorners &r_removed)
539{
540 int face_size = (weld_face.corner_end - weld_face.corner_start) + 1;
541 int corner_prev = -1;
542 bool changed_corner_start = false;
543 int corner = weld_face.corner_start;
544 do {
545 if (edge_src_to_target[corner_edges[corner]] == ELEM_COLLAPSED) {
546 if (face_size == 3) {
547 weld_face.face_dst = ELEM_COLLAPSED;
548 r_removed.faces++;
549 r_removed.corners += 3;
550 return 0;
551 }
552
553 if (corner == weld_face.corner_start) {
554 changed_corner_start = true;
555 }
556
557 r_removed.corners++;
558 face_size--;
559 }
560 else {
561 if (changed_corner_start) {
562 weld_face.corner_start = corner;
563 changed_corner_start = false;
564 }
565 if (corner_prev != -1) {
566 corner_next[corner_prev] = corner;
567 }
568 corner_prev = corner;
569 }
570 } while (corner++ != weld_face.corner_end);
571
572 corner_next[corner_prev] = weld_face.corner_start;
573 weld_face.corner_end = corner_prev;
574 weld_face.corners_num = face_size;
575 return face_size;
576}
577
585 const Span<int> corner_edges,
586 const int remaining_edge_ctx_num,
587 WeldMesh *r_weld_mesh)
588{
589 if (remaining_edge_ctx_num == 0) {
590 int removed_corners_num = 0;
591 for (WeldFace &weld_face : r_weld_mesh->weld_faces) {
592 removed_corners_num += weld_face.corners_num;
593 weld_face.face_dst = ELEM_COLLAPSED;
594 }
595 r_weld_mesh->removed_faces_num = r_weld_mesh->weld_faces.size();
596 r_weld_mesh->removed_corners_num = removed_corners_num;
597 return;
598 }
599
600 /* Splitting adds new faces at the end of the vector, which has enough space reserved already, so
601 * the existing faces aren't reallocated. Only the faces that already exist are visited here. */
602 WeldFace *weld_faces = r_weld_mesh->weld_faces.data();
603 const IndexRange weld_faces_src_range = r_weld_mesh->weld_faces.index_range();
604 const Span<int> edge_src_to_target = r_weld_mesh->edge_src_to_target;
605 MutableSpan<int> corner_next = r_weld_mesh->corner_next;
606
607 /* Only faces with at least 6 corners can be split into two new faces with at least 3 corners.
608 * All other faces are processed in parallel. Faces that may be split are split afterwards on a
609 * single thread, so the new faces are added in a deterministic order. */
610 constexpr int min_split_face_size = 6;
612 weld_faces_src_range,
613 1024,
615 [&](const IndexRange range, RemovedFacesAndCorners removed) {
616 for (const int i : range) {
617 const int face_size = collapse_weld_face(
618 corner_edges, edge_src_to_target, weld_faces[i], corner_next, removed);
619 if (face_size > 0 && face_size < min_split_face_size) {
621 face_size, corner_verts, &weld_faces[i], r_weld_mesh, removed);
622 }
623 }
624 return removed;
625 },
626 std::plus<>());
627
628 for (const int i : weld_faces_src_range) {
629 WeldFace &weld_face = weld_faces[i];
630 if (weld_face.face_dst == OUT_OF_CONTEXT && weld_face.corners_num >= min_split_face_size) {
632 weld_face.corners_num, corner_verts, &weld_face, r_weld_mesh, removed);
633 }
634 }
635
636 r_weld_mesh->removed_faces_num = removed.faces;
637 r_weld_mesh->removed_corners_num = removed.corners;
638
639#ifdef USE_WELD_DEBUG
640 weld_assert_removed_faces_and_corners_num(
641 *r_weld_mesh, r_weld_mesh->removed_faces_num, r_weld_mesh->removed_corners_num);
642#endif
643}
644
645static void weld_face_find_doubles(const Span<int> corner_verts, WeldMesh *r_weld_mesh)
646{
647 if (r_weld_mesh->removed_faces_num == r_weld_mesh->weld_faces.size()) {
648 return;
649 }
650
651 MutableSpan<WeldFace> weld_faces = r_weld_mesh->weld_faces;
652 const Span<int> vert_src_to_target = r_weld_mesh->vert_src_to_target;
653 const Span<int> corner_next = r_weld_mesh->corner_next;
654
655 IndexMaskMemory memory;
656 const IndexMask remaining_faces = IndexMask::from_predicate(
657 weld_faces.index_range(),
658 memory,
659 [&](const int i) { return weld_faces[i].face_dst == OUT_OF_CONTEXT; },
661
662 /* Gather the vertices of the remaining faces after merging. */
663 Array<int> face_offset_data(weld_faces.size() + 1, 0);
664 remaining_faces.foreach_index(
665 [&](const int i) { face_offset_data[i] = weld_faces[i].corners_num; },
668 face_offset_data);
669 Array<int> face_verts(face_offsets.total_size());
670 remaining_faces.foreach_index(
671 [&](const int i) {
672 int *vert = face_verts.as_mutable_span().slice(face_offsets[i]).data();
673 foreach_weld_face_corner(weld_faces[i], corner_next, [&](const int corner) {
674 *vert++ = vert_src_to_target[corner_verts[corner]];
675 });
676 },
678
679 const IndexMask duplicate_faces = bke::find_duplicate_faces(
680 face_offsets, face_verts, remaining_faces, memory);
681 duplicate_faces.foreach_index([&](const int i) { weld_faces[i].face_dst = ELEM_DUPLICATE; },
683
684 r_weld_mesh->removed_faces_num += duplicate_faces.size();
685 r_weld_mesh->removed_corners_num += offset_indices::sum_group_sizes(face_offsets,
686 duplicate_faces);
687
688#ifdef USE_WELD_DEBUG
689 weld_assert_removed_faces_and_corners_num(
690 *r_weld_mesh, r_weld_mesh->removed_faces_num, r_weld_mesh->removed_corners_num);
691#endif
692}
693
695
696/* -------------------------------------------------------------------- */
699
704 const Span<int> vert_src_to_target,
705 const Span<bool> vert_affected,
706 const int removed_verts_num,
707 WeldMesh *r_weld_mesh)
708{
710 const Span<int2> edges = mesh.edges();
711 const OffsetIndices faces = mesh.faces();
712 const Span<int> corner_verts = mesh.corner_verts();
713 const Span<int> corner_edges = mesh.corner_edges();
714
715 r_weld_mesh->removed_verts_num = removed_verts_num;
716
717 r_weld_mesh->edge_src_to_target.reinitialize(edges.size());
718 r_weld_mesh->vert_src_to_target = vert_src_to_target;
719 r_weld_mesh->vert_affected = vert_affected;
720
721#ifdef USE_WELD_DEBUG
722 r_weld_mesh->corner_verts = corner_verts;
723 r_weld_mesh->corner_edges = corner_edges;
724 r_weld_mesh->faces = faces;
725#endif
726
727 IndexMaskMemory memory;
728 int collapsed_edges_num;
729 const IndexMask weld_edges = find_collapsed_and_weld_edges(edges,
730 vert_src_to_target,
731 vert_affected,
732 memory,
733 r_weld_mesh->edge_src_to_target,
734 &collapsed_edges_num);
735 const int removed_double_edges_num = find_duplicate_edges(
736 edges, vert_src_to_target, weld_edges, mesh.verts_num, r_weld_mesh->edge_src_to_target);
737
738 r_weld_mesh->removed_edges_num = collapsed_edges_num + removed_double_edges_num;
739
740#ifdef USE_WELD_DEBUG
741 weld_assert_removed_edges_num(r_weld_mesh->edge_src_to_target, r_weld_mesh->removed_edges_num);
742#endif
743
744 weld_face_corner_ctx_alloc(faces, corner_verts, r_weld_mesh);
745
747 corner_verts, corner_edges, weld_edges.size() - removed_double_edges_num, r_weld_mesh);
748
749 weld_face_find_doubles(corner_verts, r_weld_mesh);
750}
751
753
754/* -------------------------------------------------------------------- */
757
762static IndexMask merge_survivors(const Span<int> src_to_target, IndexMaskMemory &memory)
763{
765 src_to_target.index_range(), memory, [&](const int i) { return src_to_target[i] == i; });
766}
767
782
791 const IndexMask &survivors,
792 const Span<int> src_to_dst,
793 const bool do_mix_data,
794 IndexMaskMemory &memory)
795{
798 map.dst_to_src.reinitialize(survivors.size());
799 survivors.to_indices(map.dst_to_src.as_mutable_span());
800 if (!do_mix_data) {
801 return map;
802 }
803
804 /* Elements that merge into another element. */
806 src_to_target.index_range(), memory, [&](const int i) {
807 return src_to_target[i] != i && src_to_target[i] >= 0;
808 });
809 if (merged.is_empty()) {
810 return map;
811 }
812
813 /* Only the merged elements are grouped by their result element here, since grouping the
814 * targets as well is significantly slower than inserting them afterwards. */
815 Array<int> merged_dst(merged.size());
816 array_utils::gather(GSpan(src_to_dst), merged, GMutableSpan(merged_dst.as_mutable_span()));
817 Array<int> merged_offset_data;
818 Array<int> merged_index_data;
820 merged_dst, survivors.size(), merged_offset_data, merged_index_data, merged);
821
822 map.mixed = IndexMask::from_predicate(IndexRange(survivors.size()), memory, [&](const int dst) {
823 return !merged_by_dst[dst].is_empty();
824 });
825 map.mixed_offsets.reinitialize(map.mixed.size() + 1);
827 [&](const int dst, const int pos) {
828 /* The target is part of the group too. */
829 map.mixed_offsets[pos] = merged_by_dst[dst].size() + 1;
830 },
833 map.mixed_offsets);
834
835 /* Each group starts with the target, followed by the elements that merge into it. */
836 map.mixed_indices.reinitialize(mixed_offsets.total_size());
838 [&](const int dst, const int pos) {
839 MutableSpan<int> group = map.mixed_indices.as_mutable_span().slice(mixed_offsets[pos]);
840 group.first() = map.dst_to_src[dst];
841 group.drop_front(1).copy_from(merged_by_dst[dst]);
842 },
844 return map;
845}
846
851static Array<int> merge_src_to_dst_map(const Span<int> src_to_target, const IndexMask &survivors)
852{
854 Array<int> src_to_dst(src_to_target.size());
855 index_mask::build_reverse_map<int>(survivors, src_to_dst);
856
857 threading::parallel_for(src_to_target.index_range(), 4096, [&](const IndexRange range) {
858 for (const int i : range) {
859 const int elem_target = src_to_target[i];
860 if (elem_target != i) {
861 /* Collapsed elements have no target. Any value will do, it's never read. */
862 src_to_dst[i] = elem_target >= 0 ? src_to_dst[elem_target] : 0;
863 }
864 }
865 });
866 return src_to_dst;
867}
868
870
871/* -------------------------------------------------------------------- */
874
880static void copy_and_mix_attributes(const bke::AttributeAccessor src_attributes,
881 const bke::AttrDomain domain,
882 const bke::AttributeFilter &attribute_filter,
883 const MergePropagationMap &map,
884 bke::MutableAttributeAccessor dst_attributes)
885{
886 if (map.mixed.is_empty()) {
888 src_attributes, domain, domain, attribute_filter, map.dst_to_src, dst_attributes);
889 return;
890 }
891 src_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
892 if (iter.domain != domain) {
893 return;
894 }
895 if (iter.data_type == bke::AttrType::String) {
896 return;
897 }
898 if (attribute_filter.allow_skip(iter.name)) {
899 return;
900 }
901 const GVArray src_attr = *iter.get();
902 const CommonVArrayInfo info = src_attr.common_info();
904 const bke::AttributeInitValue init(GPointer(src_attr.type(), info.data));
905 if (dst_attributes.add(iter.name, iter.domain, iter.data_type, init)) {
906 return;
907 }
908 }
909 const GVArraySpan src_span(src_attr);
911 iter.name, iter.domain, iter.data_type);
912 bke::attribute_math::gather(src_span, map.dst_to_src.as_span(), dst_attr.span);
913 const GroupedSpan<int> mixed_groups = map.mixed_groups();
915 src_span, mixed_groups.offsets, mixed_groups.data, std::nullopt, map.mixed, dst_attr.span);
916 dst_attr.finish();
917 });
918}
919
920static void mix_vertex_groups(const Mesh &mesh_src, const MergePropagationMap &map, Mesh &mesh_dst)
921{
922 const Span<MDeformVert> src_dverts = mesh_src.deform_verts();
923 if (src_dverts.is_empty()) {
924 return;
925 }
926 MutableSpan<MDeformVert> dst_dverts = mesh_dst.deform_verts_for_write();
927 const GroupedSpan<int> mixed_groups = map.mixed_groups();
928 IndexMaskMemory memory;
929 const IndexMask copied = map.mixed.complement(dst_dverts.index_range(), memory);
930 bke::gather_deform_verts(src_dverts, map.dst_to_src, copied, dst_dverts);
931 threading::parallel_for(map.mixed.index_range(), 256, [&](const IndexRange range) {
932 bke::MDeformWeightSet weights;
933 map.mixed.slice(range).foreach_index([&](const int dst_vert, const int pos) {
934 dst_dverts[dst_vert] = mix_deform_verts(src_dverts, mixed_groups[range[pos]], {}, weights);
935 });
936 });
937}
938
940{
941 Set<StringRef> names;
942 for (bDeformGroup &group : mesh.vertex_group_names) {
943 names.add(group.name);
944 }
945 return names;
946}
947
949 const Span<int> vert_src_to_target,
950 const int removed_vertex_count,
951 const bool do_mix_data,
952 const bke::AttributeFilter &attribute_filter)
953{
955#ifdef USE_WELD_DEBUG_TIME
956 SCOPED_TIMER(__func__);
957#endif
958
959 const Span<int2> src_edges = mesh.edges();
960 const OffsetIndices src_faces = mesh.faces();
961 const Span<int> src_corner_verts = mesh.corner_verts();
962 const Span<int> src_corner_edges = mesh.corner_edges();
963 const bke::AttributeAccessor src_attributes = mesh.attributes();
964 const int src_verts_num = mesh.verts_num;
965 const int src_edges_num = mesh.edges_num;
966
967 const Array<bool> vert_affected = find_affected_verts(vert_src_to_target);
968
969 WeldMesh weld_mesh;
971 mesh, vert_src_to_target, vert_affected, removed_vertex_count, &weld_mesh);
972
973 const int dst_verts_num = src_verts_num - weld_mesh.removed_verts_num;
974 const int dst_edges_num = src_edges_num - weld_mesh.removed_edges_num;
975 const int dst_corners_num = src_corner_verts.size() - weld_mesh.removed_corners_num;
976 const int dst_faces_num = src_faces.size() - weld_mesh.removed_faces_num +
977 weld_mesh.new_faces_num;
978
979 Mesh *result = BKE_mesh_new_nomain(dst_verts_num, dst_edges_num, dst_faces_num, dst_corners_num);
981 MutableSpan<int2> dst_edges = result->edges_for_write();
982 MutableSpan<int> dst_face_offsets = result->face_offsets_for_write();
983 MutableSpan<int> dst_corner_verts = result->corner_verts_for_write();
984 MutableSpan<int> dst_corner_edges = result->corner_edges_for_write();
985 bke::MutableAttributeAccessor dst_attributes = result->attributes_for_write();
986
987 /* Vertices. */
988
989 IndexMaskMemory mask_memory;
990 const IndexMask vert_survivors = merge_survivors(vert_src_to_target, mask_memory);
991 BLI_assert(vert_survivors.size() == dst_verts_num);
992
993 const Array<int> vert_src_to_dst = merge_src_to_dst_map(vert_src_to_target, vert_survivors);
995 vert_src_to_target, vert_survivors, vert_src_to_dst, do_mix_data, mask_memory);
996
997 const Set<StringRef> vertex_group_names = get_vertex_group_names(mesh);
999 src_attributes,
1001 bke::attribute_filter_with_skip_ref(attribute_filter, vertex_group_names),
1002 vert_map,
1003 dst_attributes);
1004 mix_vertex_groups(mesh, vert_map, *result);
1005 if (CustomData_has_layer(&mesh.vert_data, CD_ORIGINDEX)) {
1006 const Span src(static_cast<const int *>(CustomData_get_layer(&mesh.vert_data, CD_ORIGINDEX)),
1007 mesh.verts_num);
1008 MutableSpan dst(static_cast<int *>(CustomData_add_layer(
1009 &result->vert_data, CD_ORIGINDEX, CD_CONSTRUCT, result->verts_num)),
1010 result->verts_num);
1011 array_utils::gather(src, vert_map.dst_to_src.as_span(), dst);
1012 }
1013
1014 /* Edges. */
1015
1016 const IndexMask edge_survivors = merge_survivors(weld_mesh.edge_src_to_target, mask_memory);
1017 BLI_assert(edge_survivors.size() == dst_edges_num);
1018
1019 const Array<int> edge_src_to_dst = merge_src_to_dst_map(weld_mesh.edge_src_to_target,
1020 edge_survivors);
1022 weld_mesh.edge_src_to_target, edge_survivors, edge_src_to_dst, do_mix_data, mask_memory);
1023
1024 copy_and_mix_attributes(src_attributes,
1026 bke::attribute_filter_with_skip_ref(attribute_filter, {".edge_verts"}),
1027 edge_map,
1028 dst_attributes);
1029 if (CustomData_has_layer(&mesh.edge_data, CD_ORIGINDEX)) {
1030 const Span src(static_cast<const int *>(CustomData_get_layer(&mesh.edge_data, CD_ORIGINDEX)),
1031 mesh.edges_num);
1032 MutableSpan dst(static_cast<int *>(CustomData_add_layer(
1033 &result->edge_data, CD_ORIGINDEX, CD_CONSTRUCT, result->edges_num)),
1034 result->edges_num);
1035 array_utils::gather(src, edge_map.dst_to_src.as_span(), dst);
1036 }
1037
1038 threading::parallel_for(dst_edges.index_range(), 2048, [&](const IndexRange range) {
1039 for (const int dst_edge_index : range) {
1040 const int2 src_edge = src_edges[edge_map.dst_to_src[dst_edge_index]];
1041 dst_edges[dst_edge_index] = int2(vert_src_to_dst[src_edge[0]], vert_src_to_dst[src_edge[1]]);
1042 }
1043 });
1044
1045 /* Faces and corners. */
1046
1047 const Span<WeldFace> weld_faces = weld_mesh.weld_faces;
1048 const Span<int> corner_next = weld_mesh.corner_next;
1049
1050 /* The source faces that remain keep their order, followed by the new faces created by splitting
1051 * source faces. */
1052 const IndexMask kept_src_faces = IndexMask::from_predicate(
1053 src_faces.index_range(),
1054 mask_memory,
1055 [&](const int face) {
1056 const int face_ctx = weld_mesh.face_to_weld_face[face];
1057 return face_ctx == OUT_OF_CONTEXT || weld_faces[face_ctx].face_dst == OUT_OF_CONTEXT;
1058 },
1059 exec_mode::grain_size(4096));
1060 const IndexMask kept_new_faces = IndexMask::from_predicate(
1061 weld_faces.index_range().take_back(weld_mesh.new_faces_num),
1062 mask_memory,
1063 [&](const int weld_face) { return weld_faces[weld_face].face_dst == OUT_OF_CONTEXT; },
1064 exec_mode::grain_size(4096));
1065 BLI_assert(kept_src_faces.size() + kept_new_faces.size() == dst_faces_num);
1066 const IndexRange dst_new_faces(kept_src_faces.size(), kept_new_faces.size());
1067
1068 kept_src_faces.foreach_index(
1069 [&](const int src_face, const int dst_face) {
1070 const int face_ctx = weld_mesh.face_to_weld_face[src_face];
1071 dst_face_offsets[dst_face] = face_ctx == OUT_OF_CONTEXT ? src_faces[src_face].size() :
1072 weld_faces[face_ctx].corners_num;
1073 },
1074 exec_mode::grain_size(4096));
1075 kept_new_faces.foreach_index(
1076 [&](const int weld_face, const int pos) {
1077 dst_face_offsets[dst_new_faces[pos]] = weld_faces[weld_face].corners_num;
1078 },
1079 exec_mode::grain_size(4096));
1080 if (!dst_face_offsets.is_empty()) {
1081 offset_indices::accumulate_counts_to_offsets(dst_face_offsets);
1082 }
1083 const OffsetIndices dst_faces = result->faces();
1084 BLI_assert(dst_faces.total_size() == dst_corners_num);
1085
1086 /* The source corners merged into a result corner are the corners of the source face with the
1087 * same vertex after merging. Only corners with affected vertices can have more than one. */
1088 const auto foreach_corner_in_group =
1089 [&](const IndexRange src_face, const int corner, const auto &fn) {
1090 const int vert = vert_src_to_target[src_corner_verts[corner]];
1091 if (!vert_affected[vert]) {
1092 fn(corner);
1093 return;
1094 }
1095 for (const int group_corner : src_face) {
1096 if (vert_src_to_target[src_corner_verts[group_corner]] == vert) {
1097 fn(group_corner);
1098 }
1099 }
1100 };
1101
1102 /* Count the result corners of every weld face that are created from multiple source corners,
1103 * and their source corners, so that only those need groups for mixing attribute values. */
1104 Array<int> mixed_corner_offset_data(weld_faces.size() + 1, 0);
1105 Array<int> mixed_source_offset_data(weld_faces.size() + 1, 0);
1106 threading::parallel_for(weld_faces.index_range(), 1024, [&](const IndexRange range) {
1107 for (const int i : range) {
1108 const WeldFace &weld_face = weld_faces[i];
1109 if (weld_face.face_dst != OUT_OF_CONTEXT) {
1110 continue;
1111 }
1112 const IndexRange src_face = src_faces[weld_face.face_src];
1113 foreach_weld_face_corner(weld_face, corner_next, [&](const int corner) {
1114 int group_size = 0;
1115 foreach_corner_in_group(
1116 src_face, corner, [&](const int /*group_corner*/) { group_size++; });
1117 if (group_size > 1) {
1118 mixed_corner_offset_data[i]++;
1119 mixed_source_offset_data[i] += group_size;
1120 }
1121 });
1122 }
1123 });
1124 const OffsetIndices mixed_corners_by_weld_face = offset_indices::accumulate_counts_to_offsets(
1125 mixed_corner_offset_data);
1126 const OffsetIndices mixed_sources_by_weld_face = offset_indices::accumulate_counts_to_offsets(
1127 mixed_source_offset_data);
1128
1129 MergePropagationMap corner_map;
1130 corner_map.dst_to_src.reinitialize(dst_corners_num);
1131 Array<int> mixed_dst_corners(mixed_corners_by_weld_face.total_size());
1132 corner_map.mixed_offsets.reinitialize(mixed_corners_by_weld_face.total_size() + 1);
1133 corner_map.mixed_indices.reinitialize(mixed_sources_by_weld_face.total_size());
1134 corner_map.mixed_offsets.last() = corner_map.mixed_indices.size();
1135
1136 const auto fill_weld_face = [&](const int weld_face_index, const IndexRange dst_face) {
1137 const WeldFace &weld_face = weld_faces[weld_face_index];
1138 const IndexRange src_face = src_faces[weld_face.face_src];
1139 int dst_corner = dst_face.start();
1140 int mixed_corner = mixed_corners_by_weld_face[weld_face_index].start();
1141 int mixed_source = mixed_sources_by_weld_face[weld_face_index].start();
1142 foreach_weld_face_corner(weld_face, corner_next, [&](const int corner) {
1143 const int vert = vert_src_to_target[src_corner_verts[corner]];
1144 const int edge = weld_mesh.edge_src_to_target[src_corner_edges[corner]];
1145 dst_corner_verts[dst_corner] = vert_src_to_dst[vert];
1146 dst_corner_edges[dst_corner] = edge_src_to_dst[edge];
1147
1148 int group_size = 0;
1149 foreach_corner_in_group(src_face, corner, [&](const int group_corner) {
1150 if (group_size++ == 0) {
1151 corner_map.dst_to_src[dst_corner] = group_corner;
1152 }
1153 });
1154 if (group_size > 1) {
1155 mixed_dst_corners[mixed_corner] = dst_corner;
1156 corner_map.mixed_offsets[mixed_corner] = mixed_source;
1157 foreach_corner_in_group(src_face, corner, [&](const int group_corner) {
1158 corner_map.mixed_indices[mixed_source++] = group_corner;
1159 });
1160 mixed_corner++;
1161 }
1162 dst_corner++;
1163 });
1164 BLI_assert(dst_corner == dst_face.one_after_last());
1165 };
1166
1167 kept_src_faces.foreach_index(
1168 [&](const int src_face_index, const int dst_face_index) {
1169 const IndexRange dst_face = dst_faces[dst_face_index];
1170 const int face_ctx = weld_mesh.face_to_weld_face[src_face_index];
1171 if (face_ctx != OUT_OF_CONTEXT) {
1172 fill_weld_face(face_ctx, dst_face);
1173 return;
1174 }
1175 const IndexRange src_face = src_faces[src_face_index];
1176 for (const int i : src_face.index_range()) {
1177 dst_corner_verts[dst_face[i]] = vert_src_to_dst[src_corner_verts[src_face[i]]];
1178 dst_corner_edges[dst_face[i]] = edge_src_to_dst[src_corner_edges[src_face[i]]];
1179 corner_map.dst_to_src[dst_face[i]] = src_face[i];
1180 }
1181 },
1182 exec_mode::grain_size(512));
1183 kept_new_faces.foreach_index(
1184 [&](const int weld_face, const int pos) {
1185 fill_weld_face(weld_face, dst_faces[dst_new_faces[pos]]);
1186 },
1187 exec_mode::grain_size(512));
1188 corner_map.mixed = IndexMask::from_indices(mixed_dst_corners.as_span(), mask_memory);
1189
1190 /* Face attributes. New faces get default values. */
1191 src_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
1192 if (iter.domain != bke::AttrDomain::Face) {
1193 return;
1194 }
1195 if (attribute_filter.allow_skip(iter.name)) {
1196 return;
1197 }
1198 const bke::GAttributeReader src_attr = iter.get();
1199 const CommonVArrayInfo info = src_attr.varray.common_info();
1200 if (info.type == CommonVArrayInfo::Type::Single) {
1201 const bke::AttributeInitValue init(GPointer(src_attr.varray.type(), info.data));
1202 if (dst_attributes.add(iter.name, iter.domain, iter.data_type, init)) {
1203 return;
1204 }
1205 }
1206 if (kept_src_faces.size() == src_faces.size() && dst_new_faces.is_empty() &&
1207 src_attr.sharing_info && src_attr.varray.is_span())
1208 {
1209 const bke::AttributeInitShared init(src_attr.varray.get_internal_span().data(),
1210 *src_attr.sharing_info);
1211 if (dst_attributes.add(iter.name, iter.domain, iter.data_type, init)) {
1212 return;
1213 }
1214 }
1215 const CPPType &type = src_attr.varray.type();
1216 bke::GSpanAttributeWriter dst_attr = dst_attributes.lookup_or_add_for_write_only_span(
1217 iter.name, iter.domain, iter.data_type);
1218 array_utils::gather(
1219 src_attr.varray, kept_src_faces, dst_attr.span.take_front(kept_src_faces.size()));
1220 GMutableSpan default_data = dst_attr.span.slice(dst_new_faces);
1221 type.fill_assign_n(type.default_value(), default_data.data(), default_data.size());
1222 dst_attr.finish();
1223 });
1224
1225 if (CustomData_has_layer(&mesh.face_data, CD_ORIGINDEX)) {
1226 const Span src(static_cast<const int *>(CustomData_get_layer(&mesh.face_data, CD_ORIGINDEX)),
1227 mesh.faces_num);
1228 MutableSpan dst(static_cast<int *>(CustomData_add_layer(
1229 &result->face_data, CD_ORIGINDEX, CD_CONSTRUCT, result->faces_num)),
1230 result->faces_num);
1231 array_utils::gather(
1232 GSpan(src), kept_src_faces, GMutableSpan(dst.take_front(kept_src_faces.size())));
1233 dst.slice(dst_new_faces).fill(ORIGINDEX_NONE);
1234 }
1235
1237 src_attributes,
1238 bke::AttrDomain::Corner,
1239 bke::attribute_filter_with_skip_ref(attribute_filter, {".corner_vert", ".corner_edge"}),
1240 corner_map,
1241 dst_attributes);
1242 if (const auto *src = static_cast<const float2 *>(
1243 CustomData_get_layer(&mesh.corner_data, CD_ORIGSPACE_MLOOP)))
1244 {
1245 float2 *dst = static_cast<float2 *>(CustomData_add_layer(
1246 &result->corner_data, CD_ORIGSPACE_MLOOP, CD_CONSTRUCT, result->corners_num));
1247 const Span src_span(src, mesh.corners_num);
1248 const MutableSpan dst_span(dst, result->corners_num);
1249 array_utils::gather(src_span, corner_map.dst_to_src.as_span(), dst_span);
1250 const GroupedSpan<int> mixed_groups = corner_map.mixed_groups();
1251 bke::attribute_math::mix_groups(GSpan(src_span),
1252 mixed_groups.offsets,
1253 mixed_groups.data,
1254 std::nullopt,
1255 corner_map.mixed,
1256 GMutableSpan(dst_span));
1257 }
1258
1259 for (const eCustomDataType type : {CD_MDISPS, CD_GRID_PAINT_MASK}) {
1260 if (!CustomData_has_layer(&mesh.corner_data, type)) {
1261 continue;
1262 }
1263 CustomData_add_layer(&result->corner_data, type, CD_CONSTRUCT, result->corners_num);
1264 for (const int dst_corner : IndexRange(result->corners_num)) {
1265 CustomData_copy_layer_type_data(&mesh.corner_data,
1266 &result->corner_data,
1267 type,
1268 corner_map.dst_to_src[dst_corner],
1269 dst_corner,
1270 1);
1271 }
1272 }
1273
1275
1276 return result;
1277}
1278
1280
1281/* -------------------------------------------------------------------- */
1284
1285std::optional<Mesh *> mesh_merge_by_distance_all(const Mesh &mesh,
1286 const IndexMask &selection,
1287 const float merge_distance,
1288 const bke::AttributeFilter &attribute_filter)
1289{
1290 Array<int> vert_src_to_target(mesh.verts_num, OUT_OF_CONTEXT);
1291 KDTreeNew<float3> tree(mesh.vert_positions(), selection);
1292 const int removed_verts_num = kdtree::calc_duplicates(
1293 tree, merge_distance, selection, vert_src_to_target);
1294 if (removed_verts_num == 0) {
1295 return std::nullopt;
1296 }
1297
1298 /* The KD-tree leaves vertices that aren't merged at -1. */
1299 threading::parallel_for(vert_src_to_target.index_range(), 4096, [&](const IndexRange range) {
1300 for (const int vert : range) {
1301 if (vert_src_to_target[vert] == OUT_OF_CONTEXT) {
1302 vert_src_to_target[vert] = vert;
1303 }
1304 }
1305 });
1306
1307 return create_merged_mesh(mesh, vert_src_to_target, removed_verts_num, true, attribute_filter);
1308}
1309
1311 float co[3];
1313};
1314
1316 const Mesh &mesh,
1317 Span<bool> selection,
1318 const float merge_distance,
1319 const bool only_loose_edges,
1320 const bke::AttributeFilter &attribute_filter)
1321{
1322 const Span<float3> positions = mesh.vert_positions();
1323 const Span<int2> edges = mesh.edges();
1324
1325 int removed_verts_num = 0;
1326
1327 /* From the source index of the vertex.
1328 * This indicates which vert it is or is going to be merged. */
1329 Array<int> vert_src_to_target(mesh.verts_num);
1330
1331 Array<WeldVertexCluster> vert_clusters(mesh.verts_num);
1332
1333 for (const int i : positions.index_range()) {
1334 WeldVertexCluster &cluster = vert_clusters[i];
1335 copy_v3_v3(cluster.co, positions[i]);
1336 cluster.merged_verts = 0;
1337 }
1338 const float merge_dist_sq = square_f(merge_distance);
1339
1340 array_utils::fill_index_range(vert_src_to_target.as_mutable_span());
1341
1342 /* Collapse Edges that are shorter than the threshold. */
1343
1344 const IndexMask mask = only_loose_edges ? mesh.loose_edges() : IndexMask(mesh.edges().size());
1345
1346 mask.foreach_index([&](const int i) {
1347 int vert_1 = edges[i][0];
1348 int vert_2 = edges[i][1];
1349
1350 while (vert_1 != vert_src_to_target[vert_1]) {
1351 vert_1 = vert_src_to_target[vert_1];
1352 }
1353 while (vert_2 != vert_src_to_target[vert_2]) {
1354 vert_2 = vert_src_to_target[vert_2];
1355 }
1356 if (vert_1 == vert_2) {
1357 return;
1358 }
1359 if (!selection.is_empty() && (!selection[vert_1] || !selection[vert_2])) {
1360 return;
1361 }
1362 if (vert_1 > vert_2) {
1363 std::swap(vert_1, vert_2);
1364 }
1365 WeldVertexCluster *cluster_1 = &vert_clusters[vert_1];
1366 WeldVertexCluster *cluster_2 = &vert_clusters[vert_2];
1367
1368 float edge_dir[3];
1369 sub_v3_v3v3(edge_dir, cluster_2->co, cluster_1->co);
1370 const float dist_sq = len_squared_v3(edge_dir);
1371 if (dist_sq <= merge_dist_sq) {
1372 float influence = (cluster_2->merged_verts + 1) /
1373 float(cluster_1->merged_verts + cluster_2->merged_verts + 2);
1374 madd_v3_v3fl(cluster_1->co, edge_dir, influence);
1375
1376 cluster_1->merged_verts += cluster_2->merged_verts + 1;
1377 vert_src_to_target[vert_2] = vert_1;
1378 removed_verts_num++;
1379 }
1380 });
1381
1382 if (removed_verts_num == 0) {
1383 return std::nullopt;
1384 }
1385
1386 /* Collapse chains built above, since chained mappings aren't supported. */
1387 for (const int i : IndexRange(mesh.verts_num)) {
1388 int vert = i;
1389 while (vert != vert_src_to_target[vert]) {
1390 vert = vert_src_to_target[vert];
1391 }
1392 vert_src_to_target[i] = vert;
1393 }
1394
1395 return create_merged_mesh(mesh, vert_src_to_target, removed_verts_num, true, attribute_filter);
1396}
1397
1399 const Span<int> vert_src_to_target,
1400 const int removed_verts_num,
1401 const bool do_mix_data)
1402{
1403 BLI_assert(vert_src_to_target.size() == mesh.verts_num);
1404 return create_merged_mesh(mesh,
1405 vert_src_to_target,
1406 removed_verts_num,
1407 do_mix_data,
1409}
1410
1412
1413std::optional<Mesh *> mesh_merge_verts(const Mesh &mesh,
1414 const IndexMask &selection,
1415 const Span<int> merge_ids,
1416 const bke::AttributeFilter &attribute_filter)
1417{
1418 Array<int> group_indices(selection.size());
1419 Vector<int> first_verts;
1420 const int groups_num = array_utils::group_ids_to_indices(
1421 merge_ids, selection, group_indices, &first_verts);
1422 const int removed_verts_num = selection.size() - groups_num;
1423 if (removed_verts_num == 0) {
1424 return std::nullopt;
1425 }
1426
1427 /* Every vertex merges into the first vertex with the same ID. */
1428 Array<int> vert_src_to_target(mesh.verts_num);
1429 array_utils::fill_index_range(vert_src_to_target.as_mutable_span());
1430 selection.foreach_index_optimized<int>(
1431 [&](const int i, const int pos) { vert_src_to_target[i] = first_verts[group_indices[pos]]; },
1432 exec_mode::grain_size(8192));
1433
1434 return create_merged_mesh(mesh, vert_src_to_target, removed_verts_num, true, attribute_filter);
1435}
1436
1437} // namespace blender::geometry
CustomData interface, see also DNA_customdata_types.h.
#define ORIGINDEX_NONE
support for deformation groups and hooks.
#define SCOPED_TIMER(name)
Definition BLI_timeit.hh:64
Object is a sort of wrapper for general info.
#define PRF_scope(category)
#define BLI_assert(a)
void init()
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
IndexRange index_range() const
Definition BLI_array.hh:371
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
CommonVArrayInfo common_info() const
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_difference(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
constexpr IndexRange take_back(int64_t n) const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan drop_front(const int64_t n) const
Definition BLI_span.hh:613
constexpr T & first() const
Definition BLI_span.hh:685
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
bool add(const Key &key)
Definition BLI_set.hh:248
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
void foreach_attribute(const FunctionRef< void(const AttributeIter &)> fn) const
GAttributeReader get() 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_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
void to_indices(MutableSpan< T > r_indices) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
#define ELEM_DUPLICATE
#define ELEM_COLLAPSED
#define OUT_OF_CONTEXT
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
void fill_index_range(MutableSpan< T > span, const T start=0)
int group_ids_to_indices(Span< int > ids, const IndexMask &mask, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices=nullptr)
void gather(GSpan src, Span< int > map, GMutableSpan dst)
void mix_groups(GSpan src, OffsetIndices< int > groups, Span< int > all_indices, std::optional< Span< float > > all_weights, GMutableSpan dst)
auto attribute_filter_with_skip_ref(const AttributeFilter &filter, const Span< StringRef > skip)
IndexMask find_duplicate_faces(OffsetIndices< int > faces, Span< int > corner_verts, const IndexMask &mask, IndexMaskMemory &memory, MutableSpan< int > r_originals={})
void gather_attributes(AttributeAccessor src_attributes, AttrDomain src_domain, AttrDomain dst_domain, const AttributeFilter &attribute_filter, const IndexMask &selection, MutableAttributeAccessor dst_attributes)
void gather_deform_verts(Span< MDeformVert > src, Span< int > indices, MutableSpan< MDeformVert > dst)
Definition deform.cc:1774
constexpr ParallelGrainSize grain_size(int grain_size)
static void weld_face_split_recursive(int face_size, const Span< int > corner_verts, WeldFace *r_wp, WeldMesh *r_weld_mesh, RemovedFacesAndCorners &r_removed)
static IndexMask merge_survivors(const Span< int > src_to_target, IndexMaskMemory &memory)
static IndexMask find_collapsed_and_weld_edges(const Span< int2 > edges, const Span< int > vert_src_to_target, const Span< bool > vert_affected, IndexMaskMemory &memory, MutableSpan< int > r_edge_src_to_target, int *r_collapsed_edges_num)
static MergePropagationMap merge_propagation_map(const Span< int > src_to_target, const IndexMask &survivors, const Span< int > src_to_dst, const bool do_mix_data, IndexMaskMemory &memory)
static void copy_and_mix_attributes(const bke::AttributeAccessor src_attributes, const bke::AttrDomain domain, const bke::AttributeFilter &attribute_filter, const MergePropagationMap &map, bke::MutableAttributeAccessor dst_attributes)
static int collapse_weld_face(const Span< int > corner_edges, const Span< int > edge_src_to_target, WeldFace &weld_face, MutableSpan< int > corner_next, RemovedFacesAndCorners &r_removed)
Mesh * mesh_merge_verts(const Mesh &mesh, Span< int > vert_src_to_target, int removed_verts_num, bool do_mix_data)
static Array< int > merge_src_to_dst_map(const Span< int > src_to_target, const IndexMask &survivors)
static void weld_mesh_context_create(const Mesh &mesh, const Span< int > vert_src_to_target, const Span< bool > vert_affected, const int removed_verts_num, WeldMesh *r_weld_mesh)
void debug_randomize_mesh_order(Mesh *mesh)
Definition randomize.cc:305
static Array< bool > find_affected_verts(const Span< int > vert_src_to_target)
static void weld_face_corner_ctx_setup_collapsed_and_split(const Span< int > corner_verts, const Span< int > corner_edges, const int remaining_edge_ctx_num, WeldMesh *r_weld_mesh)
static void foreach_weld_face_corner(const WeldFace &weld_face, const Span< int > corner_next, const Fn &fn)
static int find_duplicate_edges(const Span< int2 > edges, const Span< int > vert_src_to_target, const IndexMask &weld_edges, const int verts_num, MutableSpan< int > r_edge_src_to_target)
static void mix_vertex_groups(const Mesh &mesh_src, const MergePropagationMap &map, Mesh &mesh_dst)
std::optional< Mesh * > mesh_merge_by_distance_connected(const Mesh &mesh, Span< bool > selection, float merge_distance, bool only_loose_edges, const bke::AttributeFilter &attribute_filter=bke::AttributeFilter::default_filter())
std::optional< Mesh * > mesh_merge_by_distance_all(const Mesh &mesh, const IndexMask &selection, float merge_distance, const bke::AttributeFilter &attribute_filter=bke::AttributeFilter::default_filter())
static Mesh * create_merged_mesh(const Mesh &mesh, const Span< int > vert_src_to_target, const int removed_vertex_count, const bool do_mix_data, const bke::AttributeFilter &attribute_filter)
static void weld_face_corner_ctx_alloc(const OffsetIndices< int > faces, const Span< int > corner_verts, WeldMesh *r_weld_mesh)
static void weld_face_find_doubles(const Span< int > corner_verts, WeldMesh *r_weld_mesh)
static Set< StringRef > get_vertex_group_names(const Mesh &mesh)
void build_reverse_map(const IndexMask &mask, MutableSpan< T > r_map)
Definition index_mask.cc:36
void masked_fill(MutableSpan< T > data, const T &value, const IndexMask &mask)
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
Definition kdtree.cc:867
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
int sum_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask)
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
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
Definition BLI_task.hh:127
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE void copy_v3_v3(float r[3], const float a[3])
bool CustomData_has_layer(const CustomData *data, eCustomDataType type)
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
void BKE_mesh_copy_parameters_for_eval(Mesh *me_dst, const Mesh *me_src)
Mesh * BKE_mesh_new_nomain(int verts_num, int edges_num, int faces_num, int corners_num)
const void * CustomData_get_layer(const CustomData *data, eCustomDataType type)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float square_f(float a)
void CustomData_copy_layer_type_data(const CustomData *source, CustomData *destination, eCustomDataType type, int source_index, int destination_index, int count)
void * CustomData_add_layer(CustomData *data, eCustomDataType type, eCDAllocType alloctype, int totelem)
void vert(const int vert_id, float4 &position)
static const AttributeFilter & default_filter()
bool allow_skip(const StringRef name) const
GroupedSpan< int > mixed_groups() const
friend RemovedFacesAndCorners operator+(const RemovedFacesAndCorners &a, const RemovedFacesAndCorners &b)