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