Blender V5.3
bmo_removedoubles.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
10
11#include "MEM_guardedalloc.h"
12
13#include "BLI_array.hh"
14#include "BLI_kdtree.hh"
15#include "BLI_listbase.hh"
16#include "BLI_map.hh"
17#include "BLI_math_base.hh"
18#include "BLI_math_vector_c.hh"
20#include "BLI_stack.hh"
21#include "BLI_stack_c.hh"
23
24#include "BKE_customdata.hh"
25
26#include "bmesh.hh"
28
29namespace blender {
30
31static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op, BMOpSlot *slot_targetmap)
32{
33 BMIter liter;
34 BMLoop *l, *l_tar, *l_double;
35 bool split = false;
36
37 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
38 BMVert *v_tar = static_cast<BMVert *>(BMO_slot_map_elem_get(slot_targetmap, l->v));
39 /* Ok: if `v_tar` is nullptr (e.g. not in the map) then it's
40 * a target vert, otherwise it's a double. */
41 if (v_tar) {
42 l_tar = BM_face_vert_share_loop(f, v_tar);
43
44 if (l_tar && (l_tar != l) && !BM_loop_is_adjacent(l_tar, l)) {
45 l_double = l;
46 split = true;
47 break;
48 }
49 }
50 }
51
52 if (split) {
53 BMLoop *l_new;
54 BMFace *f_new;
55
56 f_new = BM_face_split(bm, f, l_double, l_tar, &l_new, nullptr, false);
57
58 remdoubles_splitface(f, bm, op, slot_targetmap);
59 remdoubles_splitface(f_new, bm, op, slot_targetmap);
60 }
61}
62
63#define ELE_DEL 1
64#define EDGE_COL 2
65#define VERT_IN_FACE 4
66
71 BMFace *f,
72 BMOpSlot *slot_targetmap,
73 bool *r_created)
74{
75 BMEdge *e_new;
76
77 /* New ordered edges. */
79 BMEdge **edges = edges_buf.data();
80 /* New ordered verts. */
82 BMVert **verts = verts_buf.data();
83 /* Original ordered loops to copy attributes into the new face. */
85 BMLoop **loops = loops_buf.data();
86
87 STACK_DECLARE(edges);
88 STACK_DECLARE(loops);
89 STACK_DECLARE(verts);
90
91 STACK_INIT(edges, f->len);
92 STACK_INIT(loops, f->len);
93 STACK_INIT(verts, f->len);
94
95 *r_created = false;
96
97 {
98#define LOOP_MAP_VERT_INIT(l_init, v_map, is_del) \
99 v_map = l_init->v; \
100 is_del = BMO_vert_flag_test_bool(bm, v_map, ELE_DEL); \
101 if (is_del) { \
102 v_map = static_cast<BMVert *>(BMO_slot_map_elem_get(slot_targetmap, v_map)); \
103 } \
104 ((void)0)
105
106 BMLoop *l_first, *l_curr, *l_next;
107 BMVert *v_curr;
108 bool is_del_v_curr;
109
110 l_curr = l_first = BM_FACE_FIRST_LOOP(f);
111 LOOP_MAP_VERT_INIT(l_curr, v_curr, is_del_v_curr);
112
113 do {
114 BMVert *v_next;
115 bool is_del_v_next;
116
117 l_next = l_curr->next;
118 LOOP_MAP_VERT_INIT(l_next, v_next, is_del_v_next);
119
120 /* Only search for a new edge if one of the verts is mapped. */
121 if ((is_del_v_curr || is_del_v_next) == 0) {
122 e_new = l_curr->e;
123 }
124 else if (v_curr == v_next) {
125 e_new = nullptr; /* Skip. */
126 }
127 else {
128 e_new = BM_edge_exists(v_curr, v_next);
129 BLI_assert(e_new); /* Never fails. */
130 }
131
132 if (e_new) {
133 if (BMO_vert_flag_test(bm, v_curr, VERT_IN_FACE)) [[unlikely]] {
134 /* We can't make the face, bail out. */
135 STACK_CLEAR(edges);
136 goto finally;
137 }
139
140 STACK_PUSH(edges, e_new);
141 STACK_PUSH(loops, l_curr);
142 STACK_PUSH(verts, v_curr);
143 }
144
145 v_curr = v_next;
146 is_del_v_curr = is_del_v_next;
147 } while ((l_curr = l_next) != l_first);
148
149#undef LOOP_MAP_VERT_INIT
150 }
151
152finally: {
153 uint i;
154 for (i = 0; i < STACK_SIZE(verts); i++) {
156 }
157}
158
159 if (STACK_SIZE(edges) >= 3) {
160 BMFace *f_new = BM_face_exists(verts, STACK_SIZE(verts));
161 if (f_new) {
162 return f_new;
163 }
164 f_new = BM_face_create(bm, verts, edges, STACK_SIZE(edges), f, BM_CREATE_NOP);
165 BLI_assert(f_new != f);
166
167 if (f_new) {
168 uint i = 0;
169 BMLoop *l_iter, *l_first;
170 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
171 do {
172 BM_elem_attrs_copy(bm, loops[i], l_iter);
173 } while ((void)i++, (l_iter = l_iter->next) != l_first);
174
175 *r_created = true;
176 return f_new;
177 }
178 }
179
180 return nullptr;
181}
182
189{
190 BMIter iter, liter;
191 BMVert *v;
192 BMEdge *e;
193 BMLoop *l;
194 BMFace *f;
195 BMOpSlot *slot_targetmap = BMO_slot_get(op->slots_in, "targetmap");
196 const bool use_centroid = BMO_slot_bool_get(op->slots_in, "use_centroid");
197 const bool average_vert_data = BMO_slot_bool_get(op->slots_in, "average_vert_data") ||
198 use_centroid;
199
200 /* Maintain selection history. */
201 const bool has_selected = !bm->selected.is_empty();
202 const bool use_targetmap_all = has_selected;
203 Map<void *, void *> targetmap_all;
204
205 /* Used when use_centroid or average_vert_data is true. */
207
208 /* Mark merge verts for deletion. */
209 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
210 BMVert *v_dst = static_cast<BMVert *>(BMO_slot_map_elem_get(slot_targetmap, v));
211 if (v_dst == nullptr) {
212 continue;
213 }
214
216
217 /* Merge the vertex flags, else we get randomly selected/unselected verts. */
219
220 if (use_targetmap_all) {
221 BLI_assert(v != v_dst);
222 targetmap_all.add(v, v_dst);
223 }
224
225 /* Group vertices by their survivor. */
226 if (average_vert_data && LIKELY(v_dst != v)) {
227 clusters.add(v_dst, v);
228 }
229 }
230
231 if (use_centroid) {
232 /* Compute centroid for each survivor. */
233 for (const auto &item : clusters.items()) {
234 BMVert *v_dst = item.key;
235 Span<BMVert *> cluster = item.value;
236
237 float centroid[3];
238 copy_v3_v3(centroid, v_dst->co);
239 int count = 1; /* Include `v_dst`. */
240
241 for (BMVert *v_duplicate : cluster) {
242 add_v3_v3(centroid, v_duplicate->co);
243 count++;
244 }
245
246 mul_v3_fl(centroid, 1.0f / float(count));
247 copy_v3_v3(v_dst->co, centroid);
248 }
249 }
250
251 if (average_vert_data) {
252 for (const auto &item : clusters.items()) {
253 BMVert *v_dst = item.key;
254 Span<BMVert *> merged_verts = item.value;
255
256 Array<const void *> src_blocks(merged_verts.size() + 1);
257 src_blocks[0] = v_dst->head.data;
258 for (const int i : merged_verts.index_range()) {
259 src_blocks[i + 1] = merged_verts[i]->head.data;
260 }
262 &bm->vdata, src_blocks.data(), nullptr, src_blocks.size(), v_dst->head.data);
263 }
264 }
265
266 /* Check if any faces are getting their own corners merged
267 * together, split face if so. */
268 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
269 remdoubles_splitface(f, bm, op, slot_targetmap);
270 }
271
272 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
273 BMVert *v1, *v2;
274 const bool is_del_v1 = BMO_vert_flag_test_bool(bm, (v1 = e->v1), ELE_DEL);
275 const bool is_del_v2 = BMO_vert_flag_test_bool(bm, (v2 = e->v2), ELE_DEL);
276
277 if (is_del_v1 || is_del_v2) {
278 if (is_del_v1) {
279 v1 = static_cast<BMVert *>(BMO_slot_map_elem_get(slot_targetmap, v1));
280 }
281 if (is_del_v2) {
282 v2 = static_cast<BMVert *>(BMO_slot_map_elem_get(slot_targetmap, v2));
283 }
284
285 if (v1 == v2) {
287 }
288 else {
289 /* Always merge flags, even for edges we already created. */
290 BMEdge *e_new = BM_edge_exists(v1, v2);
291 if (e_new == nullptr) {
292 e_new = BM_edge_create(bm, v1, v2, e, BM_CREATE_NOP);
293 }
295 if (use_targetmap_all) {
296 BLI_assert(e != e_new);
297 targetmap_all.add(e, e_new);
298 }
299 }
300
302 }
303 }
304
305 /* Faces get "modified" by creating new faces here, then at the
306 * end the old faces are deleted. */
307 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
308 bool vert_delete = false;
309 int edge_collapse = 0;
310
311 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
312 if (BMO_vert_flag_test(bm, l->v, ELE_DEL)) {
313 vert_delete = true;
314 }
315 if (BMO_edge_flag_test(bm, l->e, EDGE_COL)) {
316 edge_collapse++;
317 }
318 }
319
320 if (vert_delete) {
321 bool use_in_place = false;
322 BMFace *f_new = nullptr;
324
325 if (f->len - edge_collapse >= 3) {
326 bool created;
327 f_new = remdoubles_createface(bm, f, slot_targetmap, &created);
328 /* Do this so we don't need to return a list of created faces. */
329 if (f_new) {
330 if (created) {
331 bmesh_face_swap_data(f_new, f);
332
333 if (bm->use_toolflags) {
334 std::swap((reinterpret_cast<BMFace_OFlag *>(f))->oflags,
335 (reinterpret_cast<BMFace_OFlag *>(f_new))->oflags);
336 }
337
339 BM_face_kill(bm, f_new);
340 use_in_place = true;
341 }
342 else {
344 }
345 }
346 }
347
348 if ((use_in_place == false) && (f_new != nullptr)) {
349 BLI_assert(f != f_new);
350 if (use_targetmap_all) {
351 targetmap_all.add(f, f_new);
352 }
353 if (bm->act_face && (f == bm->act_face)) {
354 bm->act_face = f_new;
355 }
356 }
357 }
358 }
359
360 if (has_selected) {
362 bm, &targetmap_all, &targetmap_all, &targetmap_all, true);
363 }
364
366}
367
368#define VERT_KEEP 8
369
370#define EDGE_MARK 1
371
373{
374 BMOIter siter;
375 BMIter iter;
376 BMVert *v, *vert_target;
377 BMLoop *l, *l_first = nullptr;
378 float fac;
379 int i, tot;
380
381 vert_target = static_cast<BMVert *>(
383 tot = BM_vert_face_count(vert_target);
384
385 if (!tot) {
386 return;
387 }
388
389 fac = 1.0f / tot;
390 BM_ITER_ELEM (l, &iter, vert_target, BM_LOOPS_OF_VERT) {
391 if (l_first == nullptr) {
392 l_first = l;
393 }
394
395 for (i = 0; i < bm->ldata.totlayer; i++) {
397 const int type = bm->ldata.layers[i].type;
398 const int offset = bm->ldata.layers[i].offset;
399 void *e1, *e2;
400
401 e1 = BM_ELEM_CD_GET_VOID_P(l_first, offset);
402 e2 = BM_ELEM_CD_GET_VOID_P(l, offset);
403
405
406 if (l != l_first) {
408 }
409 }
410 }
411 }
412
413 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
414 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
415 if (l == l_first) {
416 continue;
417 }
418
420 }
421 }
422}
423
425{
426 BMOIter siter;
427 BMIter iter;
428 BMVert *v;
429 BMLoop *l;
431 int i;
432
433 for (i = 0; i < bm->ldata.totlayer; i++) {
434 const int type = bm->ldata.layers[i].type;
435 const int offset = bm->ldata.layers[i].offset;
436
438 continue;
439 }
440
442
443 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
444 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
445 void *block = BM_ELEM_CD_GET_VOID_P(l, offset);
447 }
448 }
449
453
454 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
455 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
456 void *block = BM_ELEM_CD_GET_VOID_P(l, offset);
458 }
459 }
460 }
461}
462
464{
465 BMOperator weldop;
466 BMOIter siter;
467 BMVert *v, *vert_target = nullptr;
468 float vec[3];
469 BMOpSlot *slot_targetmap;
470
471 BMO_slot_vec_get(op->slots_in, "merge_co", vec);
472
473 // BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
474 BMO_op_init(bm, &weldop, op->flag, "weld_verts");
475
476 slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
477
478 vert_target = static_cast<BMVert *>(
480
481 const bool is_explicit_snap = vert_target != nullptr;
482
483 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
484 if (!vert_target) {
485 vert_target = v;
486 copy_v3_v3(vert_target->co, vec);
487 }
488 else if (v != vert_target) {
489 BMO_slot_map_elem_insert(&weldop, slot_targetmap, v, vert_target);
490 }
491 }
492
493 if (!is_explicit_snap) {
494 BMO_slot_bool_set(weldop.slots_in, "average_vert_data", true);
495 }
496
497 BMO_op_exec(bm, &weldop);
498 BMO_op_finish(bm, &weldop);
499}
500
502{
503 BMOperator weldop;
504 BMWalker walker;
505 BMIter iter;
506 BMEdge *e;
507 BLI_Stack *edge_stack;
508 BMOpSlot *slot_targetmap;
509
510 if (BMO_slot_bool_get(op->slots_in, "uvs")) {
511 BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
512 }
513
514 BMO_op_init(bm, &weldop, op->flag, "weld_verts");
515 slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
516
518
519 BMW_init(&walker,
520 bm,
523 EDGE_MARK,
525 BMW_FLAG_NOP, /* No need to use #BMW_FLAG_TEST_HIDDEN, already marked data. */
528
529 edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
530
531 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
532 float center[3];
533 int count = 0;
534 BMVert *v_tar;
535
536 zero_v3(center);
537
539 continue;
540 }
541
542 BLI_assert(BLI_stack_is_empty(edge_stack));
543
544 for (e = static_cast<BMEdge *>(BMW_begin(&walker, e->v1)); e;
545 e = static_cast<BMEdge *>(BMW_step(&walker)))
546 {
547 BLI_stack_push(edge_stack, &e);
548
549 add_v3_v3(center, e->v1->co);
550 add_v3_v3(center, e->v2->co);
551
552 count += 2;
553
554 /* Prevent adding to `slot_targetmap` multiple times. */
557 }
558
559 if (!BLI_stack_is_empty(edge_stack)) {
560 mul_v3_fl(center, 1.0f / count);
561
562 /* Snap edges to a point. for initial testing purposes anyway. */
563 e = *static_cast<BMEdge **>(BLI_stack_peek(edge_stack));
564 v_tar = e->v1;
565
566 while (!BLI_stack_is_empty(edge_stack)) {
567 uint j;
568 BLI_stack_pop(edge_stack, &e);
569
570 for (j = 0; j < 2; j++) {
571 BMVert *v_src = *((&e->v1) + j);
572
573 copy_v3_v3(v_src->co, center);
574 if ((v_src != v_tar) && !BM_elem_flag_test(v_src, BM_ELEM_TAG)) {
576 BMO_slot_map_elem_insert(&weldop, slot_targetmap, v_src, v_tar);
577 }
578 }
579 }
580 }
581 }
582
583 BLI_stack_free(edge_stack);
584
585 BMO_op_exec(bm, &weldop);
586 BMO_op_finish(bm, &weldop);
587
588 BMW_end(&walker);
589}
590
592static void bmo_collapsecon_do_layer(BMesh *bm, const int layer, const short oflag)
593{
594 const int type = bm->ldata.layers[layer].type;
595 const int offset = bm->ldata.layers[layer].offset;
596 BMIter iter, liter;
597 BMFace *f;
598 BMLoop *l, *l2;
599 BMWalker walker;
600 BLI_Stack *block_stack;
602
603 BMW_init(&walker,
604 bm,
607 oflag,
609 BMW_FLAG_NOP, /* No need to use #BMW_FLAG_TEST_HIDDEN, already marked data. */
610 layer,
612
613 block_stack = BLI_stack_new(sizeof(void *), __func__);
614
615 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
616 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
617 if (BMO_edge_flag_test(bm, l->e, oflag)) {
618 /* Walk. */
619 BLI_assert(BLI_stack_is_empty(block_stack));
620
622 for (l2 = static_cast<BMLoop *>(BMW_begin(&walker, l)); l2;
623 l2 = static_cast<BMLoop *>(BMW_step(&walker)))
624 {
625 void *block = BM_ELEM_CD_GET_VOID_P(l2, offset);
627 BLI_stack_push(block_stack, &block);
628 }
629
630 if (!BLI_stack_is_empty(block_stack)) {
634
635 /* Snap custom-data (UV, vertex-colors) points to their centroid. */
636 while (!BLI_stack_is_empty(block_stack)) {
637 void *block;
638 BLI_stack_pop(block_stack, &block);
640 }
641 }
642 }
643 }
644 }
645
646 BLI_stack_free(block_stack);
647
648 BMW_end(&walker);
649}
650
652{
653 const short oflag = EDGE_MARK;
654 int i;
655
656/* Check flags don't change once set. */
657#ifndef NDEBUG
658 int tot_test;
659#endif
660
661 if (!CustomData_has_math(&bm->ldata)) {
662 return;
663 }
664
666
667#ifndef NDEBUG
669#endif
670
671 for (i = 0; i < bm->ldata.totlayer; i++) {
674 }
675 }
676
677#ifndef NDEBUG
679#endif
680}
681
690 BMVert *const *verts,
691 const int verts_len,
692 const float dist,
693 const bool has_keep_vert)
694{
695 int *duplicates = MEM_new_array_uninitialized<int>(verts_len, __func__);
696 bool found_duplicates = false;
697 bool has_self_index = false;
698
699 KDTree<float3> *tree = kdtree_new<float3>(verts_len);
700 for (int i = 0; i < verts_len; i++) {
701 kdtree_insert<float3>(tree, i, verts[i]->co);
702 if (has_keep_vert && BMO_vert_flag_test(bm, verts[i], VERT_KEEP)) {
703 duplicates[i] = i;
704 has_self_index = true;
705 }
706 else {
707 duplicates[i] = -1;
708 }
709 }
710
712
713 /* Given a cluster of duplicates, pick the index to keep. */
714 auto deduplicate_target_calc_fn = [&verts](const int *cluster, const int cluster_num) -> int {
715 if (cluster_num == 2) {
716 /* Special case, no use in calculating centroid.
717 * Use the lowest index for stability. */
718 return (cluster[0] < cluster[1]) ? 0 : 1;
719 }
720 BLI_assert(cluster_num > 2);
721
722 float3 centroid{0.0f};
723 for (int i = 0; i < cluster_num; i++) {
724 centroid += float3(verts[cluster[i]]->co);
725 }
726 centroid /= float(cluster_num);
727
728 /* Now pick the most "central" index (with lowest index as a tie breaker). */
729 const int cluster_end = cluster_num - 1;
730 /* Assign `i_best` from the last index as this is the index where the search originated
731 * so it's most likely to be the best. */
732 int i_best = cluster_end;
733 float dist_sq_best = len_squared_v3v3(centroid, verts[cluster[i_best]]->co);
734 for (int i = 0; i < cluster_end; i++) {
735 const float dist_sq_test = len_squared_v3v3(centroid, verts[cluster[i]]->co);
736
737 if (dist_sq_test > dist_sq_best) {
738 continue;
739 }
740 if (dist_sq_test == dist_sq_best) {
741 if (cluster[i] > cluster[i_best]) {
742 continue;
743 }
744 }
745 i_best = i;
746 dist_sq_best = dist_sq_test;
747 }
748 return i_best;
749 };
750
751 found_duplicates = kdtree_calc_duplicates_cb<float3>(
752 tree, dist, duplicates, has_self_index, deduplicate_target_calc_fn) != 0;
753
755
756 if (!found_duplicates) {
757 MEM_delete(duplicates);
758 duplicates = nullptr;
759 }
760 return duplicates;
761}
762
765 BMVert *const *verts,
766 const int verts_len,
767 const float dist,
768 const bool has_keep_vert)
769{
770 int *duplicates = MEM_new_array_uninitialized<int>(verts_len, __func__);
771 bool found_duplicates = false;
772
773 Stack<int> vert_stack;
774 Map<BMVert *, int> vert_to_index_map;
775
776 for (int i = 0; i < verts_len; i++) {
777 if (has_keep_vert && BMO_vert_flag_test(bm, verts[i], VERT_KEEP)) {
778 duplicates[i] = i;
779 }
780 else {
781 duplicates[i] = -1;
782 }
783 vert_to_index_map.add(verts[i], i);
784 }
785
786 const float dist_sq = math::square(dist);
787
788 for (int i = 0; i < verts_len; i++) {
789 if (!ELEM(duplicates[i], -1, i)) {
790 continue;
791 }
792 const float *co_check = verts[i]->co;
793 BLI_assert(vert_stack.is_empty());
794 int i_check = i;
795 do {
796 BMVert *v_check = verts[i_check];
797 if (v_check->e) {
798 BMEdge *e_iter, *e_first;
799 e_first = e_iter = v_check->e;
800 do {
801 /* Edge stepping. */
802 BMVert *v_other = BM_edge_other_vert(e_iter, v_check);
803 if (len_squared_v3v3(v_other->co, co_check) < dist_sq) {
804 const int i_other = vert_to_index_map.lookup_default(v_other, -1);
805 if ((i_other != -1) && (duplicates[i_other] == -1)) {
806 duplicates[i_other] = i;
807 vert_stack.push(i_other);
808 found_duplicates = true;
809 }
810 }
811
812 /* Face stepping. */
813 if (e_iter->l) {
814 BMLoop *l_radial_iter;
815 l_radial_iter = e_iter->l;
816 do {
817 if (l_radial_iter->v != v_check) {
818 /* This face will be met from another edge. */
819 continue;
820 }
821 if (l_radial_iter->f->len <= 3) {
822 /* Edge iteration handles triangles. */
823 continue;
824 }
825
826 /* Loop over all vertices not connected to edges attached to `v_check`.
827 * For a 4 sided face, this will only check 1 vertex. */
828 BMLoop *l_iter = l_radial_iter->next->next;
829 BMLoop *l_end = l_radial_iter->prev;
830 do {
831 BMVert *v_other = l_iter->v;
832 if (len_squared_v3v3(v_other->co, co_check) < dist_sq) {
833 const int i_other = vert_to_index_map.lookup_default(v_other, -1);
834 if ((i_other != -1) && (duplicates[i_other] == -1)) {
835 duplicates[i_other] = i;
836 vert_stack.push(i_other);
837 found_duplicates = true;
838 }
839 }
840 } while ((l_iter = l_iter->next) != l_end);
841 } while ((l_radial_iter = l_radial_iter->radial_next) != e_iter->l);
842 }
843
844 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_check)) != e_first);
845 }
846 } while ((i_check = vert_stack.is_empty() ? -1 : vert_stack.pop()) != -1);
847 }
848
849 if (!found_duplicates) {
850 MEM_delete(duplicates);
851 duplicates = nullptr;
852 }
853 return duplicates;
854}
855
857 BMOperator *op,
858 BMOperator *optarget,
859 BMOpSlot *optarget_slot)
860{
861 const bool use_connected = BMO_slot_bool_get(op->slots_in, "use_connected");
862
863 const BMOpSlot *slot_verts = BMO_slot_get(op->slots_in, "verts");
864 BMVert *const *verts = reinterpret_cast<BMVert **>(slot_verts->data.buf);
865 const int verts_len = slot_verts->len;
866
867 bool has_keep_vert = false;
868
869 const float dist = BMO_slot_float_get(op->slots_in, "dist");
870
871 /* Test whether keep_verts arg exists and is non-empty. */
872 if (BMO_slot_exists(op->slots_in, "keep_verts")) {
873 BMOIter oiter;
874 has_keep_vert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != nullptr;
875 }
876
877 /* Flag keep_verts. */
878 if (has_keep_vert) {
880 }
881
882 int *duplicates = nullptr; /* `verts_len` aligned index array. */
883 if (use_connected) {
885 bm, verts, verts_len, dist, has_keep_vert);
886 }
887 else {
888 duplicates = bmesh_find_doubles_by_distance_impl(bm, verts, verts_len, dist, has_keep_vert);
889 }
890
891 /* Null when no duplicates were found. */
892 if (duplicates) {
893 for (int i = 0; i < verts_len; i++) {
894 BMVert *v_check = verts[i];
895 if (duplicates[i] == -1) {
896 /* NOP (others can use as target). */
897 }
898 else if (duplicates[i] == i) {
899 /* Keep (others can use as target). */
900 }
901 else {
902 BMVert *v_other = verts[duplicates[i]];
903 BLI_assert(ELEM(duplicates[duplicates[i]], -1, duplicates[i]));
904 BMO_slot_map_elem_insert(optarget, optarget_slot, v_check, v_other);
905 }
906 }
907 MEM_delete(duplicates);
908 }
909}
910
912{
913 BMOperator weldop;
914 BMOpSlot *slot_targetmap;
915
916 BMO_op_init(bm, &weldop, op->flag, "weld_verts");
917 slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
918 bmesh_find_doubles_common(bm, op, &weldop, slot_targetmap);
919 BMO_op_exec(bm, &weldop);
920 BMO_op_finish(bm, &weldop);
921}
922
924{
925 BMOpSlot *slot_targetmap_out;
926 slot_targetmap_out = BMO_slot_get(op->slots_out, "targetmap.out");
927 bmesh_find_doubles_common(bm, op, op, slot_targetmap_out);
928}
929
930} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
A KD-tree for nearest neighbor search.
#define STACK_CLEAR(stack)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define ELEM(...)
#define LIKELY(x)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_ELEM_CD_GET_VOID_P(ele, offset)
#define BM_elem_flag_merge_ex(ele_a, ele_b, hflag_and)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BMO_vert_flag_disable(bm, e, oflag)
#define BMO_edge_flag_test(bm, e, oflag)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_vert_flag_test(bm, e, oflag)
#define BMO_vert_flag_test_bool(bm, e, oflag)
#define BMO_face_flag_disable(bm, e, oflag)
#define BMW_NIL_LAY
#define BMW_MASK_NOP
#define EDGE_MARK
Definition bmo_bridge.cc:28
#define ELE_DEL
#define VERT_KEEP
#define LOOP_MAP_VERT_INIT(l_init, v_map, is_del)
#define EDGE_COL
#define VERT_IN_FACE
btScalar max
int64_t size() const
Definition BLI_array.hh:267
const T * data() const
Definition BLI_array.hh:323
bool add(const Key &key, const Value &value)
Definition BLI_map.hh:295
Value lookup_default(const Key &key, const Value &default_value) const
Definition BLI_map.hh:570
MapType::ItemIterator items() const
void add(const Key &key, const Value &value)
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
#define layer
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition abc_util.cc:68
T square(const T &a)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void kdtree_balance(KDTree< CoordT > *tree)
BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:253
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void * BMW_begin(BMWalker *walker, void *start)
@ BMW_LOOPDATA_ISLAND
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
void BMW_init(BMWalker *walker, BMesh *bm, int type, short mask_vert, short mask_edge, short mask_face, BMWFlag flag, int layer, BMWDelimitFlag delimit)
Initialize Walker.
void BMO_mesh_delete_oflag_context(BMesh *bm, const short oflag, const int type, FunctionRef< void()> prepare_fn)
void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL()
Definition stack.cc:141
void CustomData_bmesh_interp(CustomData *data, const void **src_blocks, const float *weights, int count, void *dst_block)
int kdtree_calc_duplicates_cb(const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, int *duplicates, const bool has_self_index, Func &&duplicates_cb)
ATTR_WARN_UNUSED_RESULT const BMVert * v
void CustomData_bmesh_copy_block(CustomData &data, void *src_block, void **dst_block)
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op)
void BMO_op_exec(BMesh *bm, BMOperator *op)
BMESH OPSTACK EXEC OP.
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
MINLINE void mul_v3_fl(float r[3], float f)
void * BMO_slot_buffer_get_single(BMOpSlot *slot)
static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op, BMOpSlot *slot_targetmap)
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
int BM_vert_face_count(const BMVert *v)
ATTR_WARN_UNUSED_RESULT const BMFlagLayer * oflags
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
void BMW_end(BMWalker *walker)
End Walker.
void BMO_slot_vec_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, float r_vec[3])
void CustomData_data_copy_value(eCustomDataType type, const void *source, void *dest)
static void bmo_collapsecon_do_layer(BMesh *bm, const int layer, const short oflag)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
void CustomData_data_multiply(eCustomDataType type, void *data, float fac)
void BMO_slot_bool_set(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, bool i)
void bmo_pointmerge_exec(BMesh *bm, BMOperator *op)
bool BMO_op_callf(BMesh *bm, int flag, const char *fmt,...)
void * BLI_stack_peek(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:172
static int * bmesh_find_doubles_by_distance_impl(BMesh *bm, BMVert *const *verts, const int verts_len, const float dist, const bool has_keep_vert)
MINLINE void zero_v3(float r[3])
BMFace * BM_face_exists(BMVert *const *varr, int len)
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
void bmo_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
MINLINE void add_v3_v3(float r[3], const float a[3])
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op)
void bmo_weld_verts_exec(BMesh *bm, BMOperator *op)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void BM_face_kill(BMesh *bm, BMFace *f)
BMFace * BM_face_split(BMesh *bm, BMFace *f, BMLoop *l_a, BMLoop *l_b, BMLoop **r_l, BMEdge *example, const bool no_double)
Face Split.
static BMFace * remdoubles_createface(BMesh *bm, BMFace *f, BMOpSlot *slot_targetmap, bool *r_created)
static int * bmesh_find_doubles_by_distance_connected_impl(BMesh *bm, BMVert *const *verts, const int verts_len, const float dist, const bool has_keep_vert)
void BM_select_history_merge_from_targetmap(BMesh *bm, Map< void *, void * > *vert_map, Map< void *, void * > *edge_map, Map< void *, void * > *face_map, const bool use_chain)
void * BMW_step(BMWalker *walker)
Step Walker.
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition stack.cc:135
BMLoop * BM_face_vert_share_loop(BMFace *f, BMVert *v)
Return the Loop Shared by Face and Vertex.
void BMO_op_init(BMesh *bm, BMOperator *op, int flag, const char *opname)
BMESH OPSTACK INIT OP.
void bmo_average_vert_facedata_exec(BMesh *bm, BMOperator *op)
int BM_iter_mesh_count_flag(const char itype, BMesh *bm, const char hflag, const bool value)
Mesh Iter Flag Count.
void BM_elem_attrs_copy(BMesh *bm, const BMCustomDataCopyMap &map, const BMVert *src, BMVert *dst)
bool CustomData_has_math(const CustomData *data)
VecBase< float, 3 > float3
void BMO_op_finish(BMesh *bm, BMOperator *op)
BMESH OPSTACK FINISH OP.
ATTR_WARN_UNUSED_RESULT const BMFlagLayer const short oflag
BLI_INLINE void BMO_slot_map_elem_insert(BMOperator *op, BMOpSlot *slot, const void *element, void *val)
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
static void bmesh_find_doubles_common(BMesh *bm, BMOperator *op, BMOperator *optarget, BMOpSlot *optarget_slot)
void CustomData_data_initminmax(eCustomDataType type, void *min, void *max)
void bmo_find_doubles_exec(BMesh *bm, BMOperator *op)
void CustomData_data_add(eCustomDataType type, void *data1, const void *data2)
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
bool CustomData_layer_has_math(const CustomData *data, int layer_n)
void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void CustomData_data_dominmax(eCustomDataType type, const void *data, void *min, void *max)
bool BMO_slot_exists(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK HAS SLOT.
void * BMO_iter_new(BMOIter *iter, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char restrictmask)
New Iterator.
void bmo_collapse_exec(BMesh *bm, BMOperator *op)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
union blender::BMOpSlot::@376352321363166111241172004263244043165250166277 data
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
struct BMEdge * e
ListBaseT< BMEditSelection > selected