1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bmesh
19 *
20 * Welding and merging functionality.
21 */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_alloca.h"
26 #include "BLI_kdtree.h"
27 #include "BLI_listbase.h"
28 #include "BLI_math.h"
29 #include "BLI_stack.h"
30 #include "BLI_utildefines_stack.h"
31
32 #include "BKE_customdata.h"
33
34 #include "bmesh.h"
35 #include "intern/bmesh_operators_private.h"
36
remdoubles_splitface(BMFace * f,BMesh * bm,BMOperator * op,BMOpSlot * slot_targetmap)37 static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op, BMOpSlot *slot_targetmap)
38 {
39 BMIter liter;
40 BMLoop *l, *l_tar, *l_double;
41 bool split = false;
42
43 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
44 BMVert *v_tar = BMO_slot_map_elem_get(slot_targetmap, l->v);
45 /* ok: if v_tar is NULL (e.g. not in the map) then it's
46 * a target vert, otherwise it's a double */
47 if (v_tar) {
48 l_tar = BM_face_vert_share_loop(f, v_tar);
49
50 if (l_tar && (l_tar != l) && !BM_loop_is_adjacent(l_tar, l)) {
51 l_double = l;
52 split = true;
53 break;
54 }
55 }
56 }
57
58 if (split) {
59 BMLoop *l_new;
60 BMFace *f_new;
61
62 f_new = BM_face_split(bm, f, l_double, l_tar, &l_new, NULL, false);
63
64 remdoubles_splitface(f, bm, op, slot_targetmap);
65 remdoubles_splitface(f_new, bm, op, slot_targetmap);
66 }
67 }
68
69 #define ELE_DEL 1
70 #define EDGE_COL 2
71 #define VERT_IN_FACE 4
72
73 /**
74 * helper function for bmo_weld_verts_exec so we can use stack memory
75 */
remdoubles_createface(BMesh * bm,BMFace * f,BMOpSlot * slot_targetmap,bool * r_created)76 static BMFace *remdoubles_createface(BMesh *bm,
77 BMFace *f,
78 BMOpSlot *slot_targetmap,
79 bool *r_created)
80 {
81 BMEdge *e_new;
82
83 /* New ordered edges. */
84 BMEdge **edges = BLI_array_alloca(edges, f->len);
85 /* New ordered verts. */
86 BMVert **verts = BLI_array_alloca(verts, f->len);
87 /* Original ordered loops to copy attributes into the new face. */
88 BMLoop **loops = BLI_array_alloca(loops, f->len);
89
90 STACK_DECLARE(edges);
91 STACK_DECLARE(loops);
92 STACK_DECLARE(verts);
93
94 STACK_INIT(edges, f->len);
95 STACK_INIT(loops, f->len);
96 STACK_INIT(verts, f->len);
97
98 *r_created = false;
99
100 {
101 #define LOOP_MAP_VERT_INIT(l_init, v_map, is_del) \
102 v_map = l_init->v; \
103 is_del = BMO_vert_flag_test_bool(bm, v_map, ELE_DEL); \
104 if (is_del) { \
105 v_map = BMO_slot_map_elem_get(slot_targetmap, v_map); \
106 } \
107 ((void)0)
108
109 BMLoop *l_first, *l_curr, *l_next;
110 BMVert *v_curr;
111 bool is_del_v_curr;
112
113 l_curr = l_first = BM_FACE_FIRST_LOOP(f);
114 LOOP_MAP_VERT_INIT(l_curr, v_curr, is_del_v_curr);
115
116 do {
117 BMVert *v_next;
118 bool is_del_v_next;
119
120 l_next = l_curr->next;
121 LOOP_MAP_VERT_INIT(l_next, v_next, is_del_v_next);
122
123 /* only search for a new edge if one of the verts is mapped */
124 if ((is_del_v_curr || is_del_v_next) == 0) {
125 e_new = l_curr->e;
126 }
127 else if (v_curr == v_next) {
128 e_new = NULL; /* skip */
129 }
130 else {
131 e_new = BM_edge_exists(v_curr, v_next);
132 BLI_assert(e_new); /* never fails */
133 }
134
135 if (e_new) {
136 if (UNLIKELY(BMO_vert_flag_test(bm, v_curr, VERT_IN_FACE))) {
137 /* we can't make the face, bail out */
138 STACK_CLEAR(edges);
139 goto finally;
140 }
141 BMO_vert_flag_enable(bm, v_curr, VERT_IN_FACE);
142
143 STACK_PUSH(edges, e_new);
144 STACK_PUSH(loops, l_curr);
145 STACK_PUSH(verts, v_curr);
146 }
147
148 v_curr = v_next;
149 is_del_v_curr = is_del_v_next;
150 } while ((l_curr = l_next) != l_first);
151
152 #undef LOOP_MAP_VERT_INIT
153 }
154
155 finally : {
156 uint i;
157 for (i = 0; i < STACK_SIZE(verts); i++) {
158 BMO_vert_flag_disable(bm, verts[i], VERT_IN_FACE);
159 }
160 }
161
162 if (STACK_SIZE(edges) >= 3) {
163 BMFace *f_new = BM_face_exists(verts, STACK_SIZE(verts));
164 if (f_new) {
165 return f_new;
166 }
167 f_new = BM_face_create(bm, verts, edges, STACK_SIZE(edges), f, BM_CREATE_NOP);
168 BLI_assert(f_new != f);
169
170 if (f_new) {
171 uint i = 0;
172 BMLoop *l_iter, *l_first;
173 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
174 do {
175 BM_elem_attrs_copy(bm, bm, loops[i], l_iter);
176 } while ((void)i++, (l_iter = l_iter->next) != l_first);
177
178 *r_created = true;
179 return f_new;
180 }
181 }
182
183 return NULL;
184 }
185
186 /**
187 * \note with 'targetmap', multiple 'keys' are currently supported,
188 * though no callers should be using.
189 * (because slot maps currently use GHash without the GHASH_FLAG_ALLOW_DUPES flag set)
190 */
bmo_weld_verts_exec(BMesh * bm,BMOperator * op)191 void bmo_weld_verts_exec(BMesh *bm, BMOperator *op)
192 {
193 BMIter iter, liter;
194 BMVert *v;
195 BMEdge *e;
196 BMLoop *l;
197 BMFace *f;
198 BMOpSlot *slot_targetmap = BMO_slot_get(op->slots_in, "targetmap");
199
200 /* Maintain selection history. */
201 const bool has_selected = !BLI_listbase_is_empty(&bm->selected);
202 const bool use_targetmap_all = has_selected;
203 GHash *targetmap_all = NULL;
204 if (use_targetmap_all) {
205 /* Map deleted to keep elem. */
206 targetmap_all = BLI_ghash_ptr_new(__func__);
207 }
208
209 /* mark merge verts for deletion */
210 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
211 BMVert *v_dst = BMO_slot_map_elem_get(slot_targetmap, v);
212 if (v_dst != NULL) {
213 BMO_vert_flag_enable(bm, v, ELE_DEL);
214
215 /* merge the vertex flags, else we get randomly selected/unselected verts */
216 BM_elem_flag_merge_ex(v, v_dst, BM_ELEM_HIDDEN);
217
218 if (use_targetmap_all) {
219 BLI_assert(v != v_dst);
220 BLI_ghash_insert(targetmap_all, v, v_dst);
221 }
222 }
223 }
224
225 /* check if any faces are getting their own corners merged
226 * together, split face if so */
227 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
228 remdoubles_splitface(f, bm, op, slot_targetmap);
229 }
230
231 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
232 BMVert *v1, *v2;
233 const bool is_del_v1 = BMO_vert_flag_test_bool(bm, (v1 = e->v1), ELE_DEL);
234 const bool is_del_v2 = BMO_vert_flag_test_bool(bm, (v2 = e->v2), ELE_DEL);
235
236 if (is_del_v1 || is_del_v2) {
237 if (is_del_v1) {
238 v1 = BMO_slot_map_elem_get(slot_targetmap, v1);
239 }
240 if (is_del_v2) {
241 v2 = BMO_slot_map_elem_get(slot_targetmap, v2);
242 }
243
244 if (v1 == v2) {
245 BMO_edge_flag_enable(bm, e, EDGE_COL);
246 }
247 else {
248 /* always merge flags, even for edges we already created */
249 BMEdge *e_new = BM_edge_exists(v1, v2);
250 if (e_new == NULL) {
251 e_new = BM_edge_create(bm, v1, v2, e, BM_CREATE_NOP);
252 }
253 BM_elem_flag_merge_ex(e_new, e, BM_ELEM_HIDDEN);
254 if (use_targetmap_all) {
255 BLI_assert(e != e_new);
256 BLI_ghash_insert(targetmap_all, e, e_new);
257 }
258 }
259
260 BMO_edge_flag_enable(bm, e, ELE_DEL);
261 }
262 }
263
264 /* faces get "modified" by creating new faces here, then at the
265 * end the old faces are deleted */
266 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
267 bool vert_delete = false;
268 int edge_collapse = 0;
269
270 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
271 if (BMO_vert_flag_test(bm, l->v, ELE_DEL)) {
272 vert_delete = true;
273 }
274 if (BMO_edge_flag_test(bm, l->e, EDGE_COL)) {
275 edge_collapse++;
276 }
277 }
278
279 if (vert_delete) {
280 bool use_in_place = false;
281 BMFace *f_new = NULL;
282 BMO_face_flag_enable(bm, f, ELE_DEL);
283
284 if (f->len - edge_collapse >= 3) {
285 bool created;
286 f_new = remdoubles_createface(bm, f, slot_targetmap, &created);
287 /* do this so we don't need to return a list of created faces */
288 if (f_new) {
289 if (created) {
290 bmesh_face_swap_data(f_new, f);
291
292 if (bm->use_toolflags) {
293 SWAP(BMFlagLayer *, ((BMFace_OFlag *)f)->oflags, ((BMFace_OFlag *)f_new)->oflags);
294 }
295
296 BMO_face_flag_disable(bm, f, ELE_DEL);
297 BM_face_kill(bm, f_new);
298 use_in_place = true;
299 }
300 else {
301 BM_elem_flag_merge_ex(f_new, f, BM_ELEM_HIDDEN);
302 }
303 }
304 }
305
306 if ((use_in_place == false) && (f_new != NULL)) {
307 BLI_assert(f != f_new);
308 if (use_targetmap_all) {
309 BLI_ghash_insert(targetmap_all, f, f_new);
310 }
311 if (bm->act_face && (f == bm->act_face)) {
312 bm->act_face = f_new;
313 }
314 }
315 }
316 }
317
318 if (has_selected) {
319 BM_select_history_merge_from_targetmap(bm, targetmap_all, targetmap_all, targetmap_all, true);
320 }
321
322 if (use_targetmap_all) {
323 BLI_ghash_free(targetmap_all, NULL, NULL);
324 }
325
326 BMO_mesh_delete_oflag_context(bm, ELE_DEL, DEL_ONLYTAGGED);
327 }
328
329 #define VERT_KEEP 8
330 #define VERT_IN 32
331
332 #define EDGE_MARK 1
333
bmo_pointmerge_facedata_exec(BMesh * bm,BMOperator * op)334 void bmo_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
335 {
336 BMOIter siter;
337 BMIter iter;
338 BMVert *v, *vert_snap;
339 BMLoop *l, *l_first = NULL;
340 float fac;
341 int i, tot;
342
343 vert_snap = BMO_slot_buffer_get_single(BMO_slot_get(op->slots_in, "vert_snap"));
344 tot = BM_vert_face_count(vert_snap);
345
346 if (!tot) {
347 return;
348 }
349
350 fac = 1.0f / tot;
351 BM_ITER_ELEM (l, &iter, vert_snap, BM_LOOPS_OF_VERT) {
352 if (l_first == NULL) {
353 l_first = l;
354 }
355
356 for (i = 0; i < bm->ldata.totlayer; i++) {
357 if (CustomData_layer_has_math(&bm->ldata, i)) {
358 const int type = bm->ldata.layers[i].type;
359 const int offset = bm->ldata.layers[i].offset;
360 void *e1, *e2;
361
362 e1 = BM_ELEM_CD_GET_VOID_P(l_first, offset);
363 e2 = BM_ELEM_CD_GET_VOID_P(l, offset);
364
365 CustomData_data_multiply(type, e2, fac);
366
367 if (l != l_first) {
368 CustomData_data_add(type, e1, e2);
369 }
370 }
371 }
372 }
373
374 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
375 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
376 if (l == l_first) {
377 continue;
378 }
379
380 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, l_first->head.data, &l->head.data);
381 }
382 }
383 }
384
bmo_average_vert_facedata_exec(BMesh * bm,BMOperator * op)385 void bmo_average_vert_facedata_exec(BMesh *bm, BMOperator *op)
386 {
387 BMOIter siter;
388 BMIter iter;
389 BMVert *v;
390 BMLoop *l /* , *firstl = NULL */;
391 CDBlockBytes min, max;
392 int i;
393
394 for (i = 0; i < bm->ldata.totlayer; i++) {
395 const int type = bm->ldata.layers[i].type;
396 const int offset = bm->ldata.layers[i].offset;
397
398 if (!CustomData_layer_has_math(&bm->ldata, i)) {
399 continue;
400 }
401
402 CustomData_data_initminmax(type, &min, &max);
403
404 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
405 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
406 void *block = BM_ELEM_CD_GET_VOID_P(l, offset);
407 CustomData_data_dominmax(type, block, &min, &max);
408 }
409 }
410
411 CustomData_data_multiply(type, &min, 0.5f);
412 CustomData_data_multiply(type, &max, 0.5f);
413 CustomData_data_add(type, &min, &max);
414
415 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
416 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
417 void *block = BM_ELEM_CD_GET_VOID_P(l, offset);
418 CustomData_data_copy_value(type, &min, block);
419 }
420 }
421 }
422 }
423
bmo_pointmerge_exec(BMesh * bm,BMOperator * op)424 void bmo_pointmerge_exec(BMesh *bm, BMOperator *op)
425 {
426 BMOperator weldop;
427 BMOIter siter;
428 BMVert *v, *vert_snap = NULL;
429 float vec[3];
430 BMOpSlot *slot_targetmap;
431
432 BMO_slot_vec_get(op->slots_in, "merge_co", vec);
433
434 // BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
435 BMO_op_init(bm, &weldop, op->flag, "weld_verts");
436
437 slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
438
439 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
440 if (!vert_snap) {
441 vert_snap = v;
442 copy_v3_v3(vert_snap->co, vec);
443 }
444 else {
445 BMO_slot_map_elem_insert(&weldop, slot_targetmap, v, vert_snap);
446 }
447 }
448
449 BMO_op_exec(bm, &weldop);
450 BMO_op_finish(bm, &weldop);
451 }
452
bmo_collapse_exec(BMesh * bm,BMOperator * op)453 void bmo_collapse_exec(BMesh *bm, BMOperator *op)
454 {
455 BMOperator weldop;
456 BMWalker walker;
457 BMIter iter;
458 BMEdge *e;
459 BLI_Stack *edge_stack;
460 BMOpSlot *slot_targetmap;
461
462 if (BMO_slot_bool_get(op->slots_in, "uvs")) {
463 BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
464 }
465
466 BMO_op_init(bm, &weldop, op->flag, "weld_verts");
467 slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
468
469 BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
470
471 BMW_init(&walker,
472 bm,
473 BMW_VERT_SHELL,
474 BMW_MASK_NOP,
475 EDGE_MARK,
476 BMW_MASK_NOP,
477 BMW_FLAG_NOP, /* no need to use BMW_FLAG_TEST_HIDDEN, already marked data */
478 BMW_NIL_LAY);
479
480 edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
481
482 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
483 float center[3];
484 int count = 0;
485 BMVert *v_tar;
486
487 zero_v3(center);
488
489 if (!BMO_edge_flag_test(bm, e, EDGE_MARK)) {
490 continue;
491 }
492
493 BLI_assert(BLI_stack_is_empty(edge_stack));
494
495 for (e = BMW_begin(&walker, e->v1); e; e = BMW_step(&walker)) {
496 BLI_stack_push(edge_stack, &e);
497
498 add_v3_v3(center, e->v1->co);
499 add_v3_v3(center, e->v2->co);
500
501 count += 2;
502
503 /* prevent adding to slot_targetmap multiple times */
504 BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
505 BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
506 }
507
508 if (!BLI_stack_is_empty(edge_stack)) {
509 mul_v3_fl(center, 1.0f / count);
510
511 /* snap edges to a point. for initial testing purposes anyway */
512 e = *(BMEdge **)BLI_stack_peek(edge_stack);
513 v_tar = e->v1;
514
515 while (!BLI_stack_is_empty(edge_stack)) {
516 uint j;
517 BLI_stack_pop(edge_stack, &e);
518
519 for (j = 0; j < 2; j++) {
520 BMVert *v_src = *((&e->v1) + j);
521
522 copy_v3_v3(v_src->co, center);
523 if ((v_src != v_tar) && !BM_elem_flag_test(v_src, BM_ELEM_TAG)) {
524 BM_elem_flag_enable(v_src, BM_ELEM_TAG);
525 BMO_slot_map_elem_insert(&weldop, slot_targetmap, v_src, v_tar);
526 }
527 }
528 }
529 }
530 }
531
532 BLI_stack_free(edge_stack);
533
534 BMO_op_exec(bm, &weldop);
535 BMO_op_finish(bm, &weldop);
536
537 BMW_end(&walker);
538 }
539
540 /* uv collapse function */
bmo_collapsecon_do_layer(BMesh * bm,const int layer,const short oflag)541 static void bmo_collapsecon_do_layer(BMesh *bm, const int layer, const short oflag)
542 {
543 const int type = bm->ldata.layers[layer].type;
544 const int offset = bm->ldata.layers[layer].offset;
545 BMIter iter, liter;
546 BMFace *f;
547 BMLoop *l, *l2;
548 BMWalker walker;
549 BLI_Stack *block_stack;
550 CDBlockBytes min, max;
551
552 BMW_init(&walker,
553 bm,
554 BMW_LOOPDATA_ISLAND,
555 BMW_MASK_NOP,
556 oflag,
557 BMW_MASK_NOP,
558 BMW_FLAG_NOP, /* no need to use BMW_FLAG_TEST_HIDDEN, already marked data */
559 layer);
560
561 block_stack = BLI_stack_new(sizeof(void *), __func__);
562
563 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
564 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
565 if (BMO_edge_flag_test(bm, l->e, oflag)) {
566 /* walk */
567 BLI_assert(BLI_stack_is_empty(block_stack));
568
569 CustomData_data_initminmax(type, &min, &max);
570 for (l2 = BMW_begin(&walker, l); l2; l2 = BMW_step(&walker)) {
571 void *block = BM_ELEM_CD_GET_VOID_P(l2, offset);
572 CustomData_data_dominmax(type, block, &min, &max);
573 BLI_stack_push(block_stack, &block);
574 }
575
576 if (!BLI_stack_is_empty(block_stack)) {
577 CustomData_data_multiply(type, &min, 0.5f);
578 CustomData_data_multiply(type, &max, 0.5f);
579 CustomData_data_add(type, &min, &max);
580
581 /* snap CD (uv, vcol) points to their centroid */
582 while (!BLI_stack_is_empty(block_stack)) {
583 void *block;
584 BLI_stack_pop(block_stack, &block);
585 CustomData_data_copy_value(type, &min, block);
586 }
587 }
588 }
589 }
590 }
591
592 BLI_stack_free(block_stack);
593
594 BMW_end(&walker);
595 }
596
bmo_collapse_uvs_exec(BMesh * bm,BMOperator * op)597 void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op)
598 {
599 const short oflag = EDGE_MARK;
600 int i;
601
602 /* check flags dont change once set */
603 #ifndef NDEBUG
604 int tot_test;
605 #endif
606
607 if (!CustomData_has_math(&bm->ldata)) {
608 return;
609 }
610
611 BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, oflag);
612
613 #ifndef NDEBUG
614 tot_test = BM_iter_mesh_count_flag(BM_EDGES_OF_MESH, bm, oflag, true);
615 #endif
616
617 for (i = 0; i < bm->ldata.totlayer; i++) {
618 if (CustomData_layer_has_math(&bm->ldata, i)) {
619 bmo_collapsecon_do_layer(bm, i, oflag);
620 }
621 }
622
623 #ifndef NDEBUG
624 BLI_assert(tot_test == BM_iter_mesh_count_flag(BM_EDGES_OF_MESH, bm, EDGE_MARK, true));
625 #endif
626 }
627
bmesh_find_doubles_common(BMesh * bm,BMOperator * op,BMOperator * optarget,BMOpSlot * optarget_slot)628 static void bmesh_find_doubles_common(BMesh *bm,
629 BMOperator *op,
630 BMOperator *optarget,
631 BMOpSlot *optarget_slot)
632 {
633 const BMOpSlot *slot_verts = BMO_slot_get(op->slots_in, "verts");
634 BMVert *const *verts = (BMVert **)slot_verts->data.buf;
635 const int verts_len = slot_verts->len;
636
637 bool has_keep_vert = false;
638 bool found_duplicates = false;
639
640 const float dist = BMO_slot_float_get(op->slots_in, "dist");
641
642 /* Test whether keep_verts arg exists and is non-empty */
643 if (BMO_slot_exists(op->slots_in, "keep_verts")) {
644 BMOIter oiter;
645 has_keep_vert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL;
646 }
647
648 /* Flag keep_verts */
649 if (has_keep_vert) {
650 BMO_slot_buffer_flag_enable(bm, op->slots_in, "keep_verts", BM_VERT, VERT_KEEP);
651 }
652
653 int *duplicates = MEM_mallocN(sizeof(int) * verts_len, __func__);
654 {
655 KDTree_3d *tree = BLI_kdtree_3d_new(verts_len);
656 for (int i = 0; i < verts_len; i++) {
657 BLI_kdtree_3d_insert(tree, i, verts[i]->co);
658 if (has_keep_vert && BMO_vert_flag_test(bm, verts[i], VERT_KEEP)) {
659 duplicates[i] = i;
660 }
661 else {
662 duplicates[i] = -1;
663 }
664 }
665
666 BLI_kdtree_3d_balance(tree);
667 found_duplicates = BLI_kdtree_3d_calc_duplicates_fast(tree, dist, false, duplicates) != 0;
668 BLI_kdtree_3d_free(tree);
669 }
670
671 if (found_duplicates) {
672 for (int i = 0; i < verts_len; i++) {
673 BMVert *v_check = verts[i];
674 if (duplicates[i] == -1) {
675 /* nop (others can use as target) */
676 }
677 else if (duplicates[i] == i) {
678 /* keep (others can use as target) */
679 }
680 else {
681 BMVert *v_other = verts[duplicates[i]];
682 BLI_assert(ELEM(duplicates[duplicates[i]], -1, duplicates[i]));
683 BMO_slot_map_elem_insert(optarget, optarget_slot, v_check, v_other);
684 }
685 }
686 }
687
688 MEM_freeN(duplicates);
689 }
690
bmo_remove_doubles_exec(BMesh * bm,BMOperator * op)691 void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op)
692 {
693 BMOperator weldop;
694 BMOpSlot *slot_targetmap;
695
696 BMO_op_init(bm, &weldop, op->flag, "weld_verts");
697 slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
698 bmesh_find_doubles_common(bm, op, &weldop, slot_targetmap);
699 BMO_op_exec(bm, &weldop);
700 BMO_op_finish(bm, &weldop);
701 }
702
bmo_find_doubles_exec(BMesh * bm,BMOperator * op)703 void bmo_find_doubles_exec(BMesh *bm, BMOperator *op)
704 {
705 BMOpSlot *slot_targetmap_out;
706 slot_targetmap_out = BMO_slot_get(op->slots_out, "targetmap.out");
707 bmesh_find_doubles_common(bm, op, op, slot_targetmap_out);
708 }
709