BMesh: use predictable order for remove-doubles
[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_stackdefines.h"
34 #include "BLI_stack.h"
35
36 #include "BKE_customdata.h"
37
38 #include "bmesh.h"
39 #include "intern/bmesh_operators_private.h"
40
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)
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
98         {
99 #define LOOP_MAP_VERT_INIT(l_init, v_map, is_del) \
100                 v_map = l_init->v; \
101                 is_del = BMO_vert_flag_test_bool(bm, v_map, ELE_DEL); \
102                 if (is_del) { \
103                         v_map = BMO_slot_map_elem_get(slot_targetmap, v_map); \
104                 } ((void)0)
105
106
107                 BMLoop *l_first, *l_curr, *l_next;
108                 BMVert *v_curr;
109                 bool is_del_v_curr;
110
111                 l_curr = l_first = BM_FACE_FIRST_LOOP(f);
112                 LOOP_MAP_VERT_INIT(l_curr, v_curr, is_del_v_curr);
113
114                 do {
115                         BMVert *v_next;
116                         bool is_del_v_next;
117
118                         l_next = l_curr->next;
119                         LOOP_MAP_VERT_INIT(l_next, v_next, is_del_v_next);
120
121                         /* only search for a new edge if one of the verts is mapped */
122                         if ((is_del_v_curr || is_del_v_next) == 0) {
123                                 e_new = l_curr->e;
124                         }
125                         else if (v_curr == v_next) {
126                                 e_new = NULL;  /* skip */
127                         }
128                         else {
129                                 e_new = BM_edge_exists(v_curr, v_next);
130                                 BLI_assert(e_new);  /* never fails */
131                         }
132
133                         if (e_new) {
134                                 if (UNLIKELY(BMO_vert_flag_test(bm, v_curr, VERT_IN_FACE))) {
135                                         /* we can't make the face, bail out */
136                                         STACK_CLEAR(edges);
137                                         goto finally;
138                                 }
139                                 BMO_vert_flag_enable(bm, v_curr, VERT_IN_FACE);
140
141                                 STACK_PUSH(edges, e_new);
142                                 STACK_PUSH(loops, l_curr);
143                                 STACK_PUSH(verts, v_curr);
144                         }
145
146                         v_curr = v_next;
147                         is_del_v_curr = is_del_v_next;
148                 } while ((l_curr = l_next) != l_first);
149
150 #undef LOOP_MAP_VERT_INIT
151
152         }
153
154 finally:
155         {
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                 if (!BM_face_exists(verts, STACK_SIZE(edges))) {
164                         BMFace *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, bm, loops[i], l_iter);
173                                 } while ((void)i++, (l_iter = l_iter->next) != l_first);
174
175                                 return f_new;
176                         }
177                 }
178         }
179
180         return NULL;
181 }
182
183
184 /**
185  * \note with 'targetmap', multiple 'keys' are currently supported, though no callers should be using.
186  * (because slot maps currently use GHash without the GHASH_FLAG_ALLOW_DUPES flag set)
187  *
188  */
189 void bmo_weld_verts_exec(BMesh *bm, BMOperator *op)
190 {
191         BMIter iter, liter;
192         BMVert *v1, *v2;
193         BMEdge *e;
194         BMLoop *l;
195         BMFace *f;
196         BMOpSlot *slot_targetmap = BMO_slot_get(op->slots_in, "targetmap");
197
198         /* mark merge verts for deletion */
199         BM_ITER_MESH (v1, &iter, bm, BM_VERTS_OF_MESH) {
200                 if ((v2 = BMO_slot_map_elem_get(slot_targetmap, v1))) {
201                         BMO_vert_flag_enable(bm, v1, ELE_DEL);
202
203                         /* merge the vertex flags, else we get randomly selected/unselected verts */
204                         BM_elem_flag_merge(v1, v2);
205                 }
206         }
207
208         /* check if any faces are getting their own corners merged
209          * together, split face if so */
210         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
211                 remdoubles_splitface(f, bm, op, slot_targetmap);
212         }
213
214         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
215                 const bool is_del_v1 = BMO_vert_flag_test_bool(bm, (v1 = e->v1), ELE_DEL);
216                 const bool is_del_v2 = BMO_vert_flag_test_bool(bm, (v2 = e->v2), ELE_DEL);
217
218                 if (is_del_v1 || is_del_v2) {
219                         if (is_del_v1)
220                                 v1 = BMO_slot_map_elem_get(slot_targetmap, v1);
221                         if (is_del_v2)
222                                 v2 = BMO_slot_map_elem_get(slot_targetmap, v2);
223
224                         if (v1 == v2) {
225                                 BMO_edge_flag_enable(bm, e, EDGE_COL);
226                         }
227                         else {
228                                 /* always merge flags, even for edges we already created */
229                                 BMEdge *e_new = BM_edge_exists(v1, v2);
230                                 if (e_new == NULL) {
231                                         e_new = BM_edge_create(bm, v1, v2, e, BM_CREATE_NOP);
232                                 }
233                                 BM_elem_flag_merge(e_new, e);
234                         }
235
236                         BMO_edge_flag_enable(bm, e, ELE_DEL);
237                 }
238         }
239
240         /* faces get "modified" by creating new faces here, then at the
241          * end the old faces are deleted */
242         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
243                 bool vert_delete = false;
244                 int  edge_collapse = 0;
245
246                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
247                         if (BMO_vert_flag_test(bm, l->v, ELE_DEL)) {
248                                 vert_delete = true;
249                         }
250                         if (BMO_edge_flag_test(bm, l->e, EDGE_COL)) {
251                                 edge_collapse++;
252                         }
253                 }
254
255                 if (vert_delete) {
256                         BMO_face_flag_enable(bm, f, ELE_DEL);
257
258                         if (f->len - edge_collapse >= 3) {
259                                 BMFace *f_new = remdoubles_createface(bm, f, slot_targetmap);
260
261                                 /* do this so we don't need to return a list of created faces */
262                                 if (f_new) {
263                                         bmesh_face_swap_data(f_new, f);
264
265                                         if (bm->use_toolflags) {
266                                                 SWAP(BMFlagLayer *, ((BMFace_OFlag *)f)->oflags, ((BMFace_OFlag *)f_new)->oflags);
267                                         }
268
269                                         BMO_face_flag_disable(bm, f, ELE_DEL);
270
271                                         BM_face_kill(bm, f_new);
272                                 }
273                         }
274                 }
275         }
276
277         BMO_mesh_delete_oflag_context(bm, ELE_DEL, DEL_ONLYTAGGED);
278 }
279
280 static int vergaverco(const void *e1, const void *e2)
281 {
282         const BMVert *v1 = *(const void **)e1, *v2 = *(const void **)e2;
283         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
284         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
285
286         if      (x1 > x2) return  1;
287         else if (x1 < x2) return -1;
288
289         const int i1 = BM_elem_index_get(v1);
290         const int i2 = BM_elem_index_get(v2);
291
292         if      (i1 > i2) return  1;
293         else if (i1 < i2) return -1;
294
295         else return 0;
296 }
297
298 // #define VERT_TESTED  1 // UNUSED
299 #define VERT_DOUBLE     2
300 #define VERT_TARGET     4
301 #define VERT_KEEP       8
302 // #define VERT_MARK    16 // UNUSED
303 #define VERT_IN         32
304
305 #define EDGE_MARK       1
306
307 void bmo_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
308 {
309         BMOIter siter;
310         BMIter iter;
311         BMVert *v, *vert_snap;
312         BMLoop *l, *l_first = NULL;
313         float fac;
314         int i, tot;
315
316         vert_snap = BMO_slot_buffer_get_single(BMO_slot_get(op->slots_in, "vert_snap"));
317         tot = BM_vert_face_count(vert_snap);
318
319         if (!tot)
320                 return;
321
322         fac = 1.0f / tot;
323         BM_ITER_ELEM (l, &iter, vert_snap, BM_LOOPS_OF_VERT) {
324                 if (l_first == NULL) {
325                         l_first = l;
326                 }
327                 
328                 for (i = 0; i < bm->ldata.totlayer; i++) {
329                         if (CustomData_layer_has_math(&bm->ldata, i)) {
330                                 const int type = bm->ldata.layers[i].type;
331                                 const int offset = bm->ldata.layers[i].offset;
332                                 void *e1, *e2;
333
334                                 e1 = BM_ELEM_CD_GET_VOID_P(l_first, offset);
335                                 e2 = BM_ELEM_CD_GET_VOID_P(l,       offset);
336                                 
337                                 CustomData_data_multiply(type, e2, fac);
338
339                                 if (l != l_first) {
340                                         CustomData_data_add(type, e1, e2);
341                                 }
342                         }
343                 }
344         }
345
346         BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
347                 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
348                         if (l == l_first) {
349                                 continue;
350                         }
351
352                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, l_first->head.data, &l->head.data);
353                 }
354         }
355 }
356
357 void bmo_average_vert_facedata_exec(BMesh *bm, BMOperator *op)
358 {
359         BMOIter siter;
360         BMIter iter;
361         BMVert *v;
362         BMLoop *l /* , *firstl = NULL */;
363         CDBlockBytes min, max;
364         int i;
365
366         for (i = 0; i < bm->ldata.totlayer; i++) {
367                 const int type = bm->ldata.layers[i].type;
368                 const int offset = bm->ldata.layers[i].offset;
369
370                 if (!CustomData_layer_has_math(&bm->ldata, i))
371                         continue;
372                 
373                 CustomData_data_initminmax(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_dominmax(type, block, &min, &max);
379                         }
380                 }
381
382                 CustomData_data_multiply(type, &min, 0.5f);
383                 CustomData_data_multiply(type, &max, 0.5f);
384                 CustomData_data_add(type, &min, &max);
385
386                 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
387                         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
388                                 void *block = BM_ELEM_CD_GET_VOID_P(l, offset);
389                                 CustomData_data_copy_value(type, &min, block);
390                         }
391                 }
392         }
393 }
394
395 void bmo_pointmerge_exec(BMesh *bm, BMOperator *op)
396 {
397         BMOperator weldop;
398         BMOIter siter;
399         BMVert *v, *vert_snap = NULL;
400         float vec[3];
401         BMOpSlot *slot_targetmap;
402         
403         BMO_slot_vec_get(op->slots_in, "merge_co", vec);
404
405         //BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
406         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
407
408         slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
409
410         BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
411                 if (!vert_snap) {
412                         vert_snap = v;
413                         copy_v3_v3(vert_snap->co, vec);
414                 }
415                 else {
416                         BMO_slot_map_elem_insert(&weldop, slot_targetmap, v, vert_snap);
417                 }
418         }
419
420         BMO_op_exec(bm, &weldop);
421         BMO_op_finish(bm, &weldop);
422 }
423
424 void bmo_collapse_exec(BMesh *bm, BMOperator *op)
425 {
426         BMOperator weldop;
427         BMWalker walker;
428         BMIter iter;
429         BMEdge *e;
430         BLI_Stack *edge_stack;
431         BMOpSlot *slot_targetmap;
432
433         if (BMO_slot_bool_get(op->slots_in, "uvs")) {
434                 BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
435         }
436
437         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
438         slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
439
440         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
441
442         BMW_init(&walker, bm, BMW_VERT_SHELL,
443                  BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP,
444                  BMW_FLAG_NOP, /* no need to use BMW_FLAG_TEST_HIDDEN, already marked data */
445                  BMW_NIL_LAY);
446
447         edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
448
449         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
450                 float center[3];
451                 int count = 0;
452                 BMVert *v_tar;
453
454                 zero_v3(center);
455
456                 if (!BMO_edge_flag_test(bm, e, EDGE_MARK))
457                         continue;
458
459                 BLI_assert(BLI_stack_is_empty(edge_stack));
460
461                 for (e = BMW_begin(&walker, e->v1); e; e = BMW_step(&walker)) {
462                         BLI_stack_push(edge_stack, &e);
463
464                         add_v3_v3(center, e->v1->co);
465                         add_v3_v3(center, e->v2->co);
466
467                         count += 2;
468
469                         /* prevent adding to slot_targetmap multiple times */
470                         BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
471                         BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
472                 }
473
474                 if (!BLI_stack_is_empty(edge_stack)) {
475                         mul_v3_fl(center, 1.0f / count);
476
477                         /* snap edges to a point.  for initial testing purposes anyway */
478                         e = *(BMEdge **)BLI_stack_peek(edge_stack);
479                         v_tar = e->v1;
480
481                         while (!BLI_stack_is_empty(edge_stack)) {
482                                 uint j;
483                                 BLI_stack_pop(edge_stack, &e);
484
485                                 for (j = 0; j < 2; j++) {
486                                         BMVert *v_src = *((&e->v1) + j);
487
488                                         copy_v3_v3(v_src->co, center);
489                                         if ((v_src != v_tar) && !BM_elem_flag_test(v_src, BM_ELEM_TAG)) {
490                                                 BM_elem_flag_enable(v_src, BM_ELEM_TAG);
491                                                 BMO_slot_map_elem_insert(&weldop, slot_targetmap, v_src, v_tar);
492                                         }
493                                 }
494                         }
495                 }
496         }
497
498         BLI_stack_free(edge_stack);
499
500         BMO_op_exec(bm, &weldop);
501         BMO_op_finish(bm, &weldop);
502
503         BMW_end(&walker);
504 }
505
506 /* uv collapse function */
507 static void bmo_collapsecon_do_layer(BMesh *bm, const int layer, const short oflag)
508 {
509         const int type = bm->ldata.layers[layer].type;
510         const int offset = bm->ldata.layers[layer].offset;
511         BMIter iter, liter;
512         BMFace *f;
513         BMLoop *l, *l2;
514         BMWalker walker;
515         BLI_Stack *block_stack;
516         CDBlockBytes min, max;
517
518         BMW_init(&walker, bm, BMW_LOOPDATA_ISLAND,
519                  BMW_MASK_NOP, oflag, BMW_MASK_NOP,
520                  BMW_FLAG_NOP, /* no need to use BMW_FLAG_TEST_HIDDEN, already marked data */
521                  layer);
522
523         block_stack = BLI_stack_new(sizeof(void *), __func__);
524
525         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
526                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
527                         if (BMO_edge_flag_test(bm, l->e, oflag)) {
528                                 /* walk */
529                                 BLI_assert(BLI_stack_is_empty(block_stack));
530
531                                 CustomData_data_initminmax(type, &min, &max);
532                                 for (l2 = BMW_begin(&walker, l); l2; l2 = BMW_step(&walker)) {
533                                         void *block = BM_ELEM_CD_GET_VOID_P(l2, offset);
534                                         CustomData_data_dominmax(type, block, &min, &max);
535                                         BLI_stack_push(block_stack, &block);
536                                 }
537
538                                 if (!BLI_stack_is_empty(block_stack)) {
539                                         CustomData_data_multiply(type, &min, 0.5f);
540                                         CustomData_data_multiply(type, &max, 0.5f);
541                                         CustomData_data_add(type, &min, &max);
542
543                                         /* snap CD (uv, vcol) points to their centroid */
544                                         while (!BLI_stack_is_empty(block_stack)) {
545                                                 void *block;
546                                                 BLI_stack_pop(block_stack, &block);
547                                                 CustomData_data_copy_value(type, &min, block);
548                                         }
549                                 }
550                         }
551                 }
552         }
553
554         BLI_stack_free(block_stack);
555
556         BMW_end(&walker);
557 }
558
559 void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op)
560 {
561         const short oflag = EDGE_MARK;
562         int i;
563
564         /* check flags dont change once set */
565 #ifndef NDEBUG
566         int tot_test;
567 #endif
568
569         if (!CustomData_has_math(&bm->ldata)) {
570                 return;
571         }
572
573         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, oflag);
574
575 #ifndef NDEBUG
576         tot_test = BM_iter_mesh_count_flag(BM_EDGES_OF_MESH, bm, oflag, true);
577 #endif
578
579         for (i = 0; i < bm->ldata.totlayer; i++) {
580                 if (CustomData_layer_has_math(&bm->ldata, i))
581                         bmo_collapsecon_do_layer(bm, i, oflag);
582         }
583
584 #ifndef NDEBUG
585         BLI_assert(tot_test == BM_iter_mesh_count_flag(BM_EDGES_OF_MESH, bm, EDGE_MARK, true));
586 #endif
587
588 }
589
590 static void bmesh_find_doubles_common(
591         BMesh *bm, BMOperator *op,
592         BMOperator *optarget, BMOpSlot *optarget_slot)
593 {
594         BMVert  **verts;
595         int       verts_len;
596
597         int i, j, keepvert = 0;
598
599         const float dist  = BMO_slot_float_get(op->slots_in, "dist");
600         const float dist_sq = dist * dist;
601         const float dist3 = ((float)M_SQRT3 + 0.00005f) * dist;   /* Just above sqrt(3) */
602
603         /* Test whether keep_verts arg exists and is non-empty */
604         if (BMO_slot_exists(op->slots_in, "keep_verts")) {
605                 BMOIter oiter;
606                 keepvert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL;
607         }
608
609         /* get the verts as an array we can sort */
610         verts = BMO_slot_as_arrayN(op->slots_in, "verts", &verts_len);
611
612         /* Ensure indices are different so we have a predictable order when values match. */
613         for (i = 0; i < verts_len; i++) {
614                 BM_elem_index_set(verts[i], i);  /* set_dirty! */
615         }
616         bm->elem_index_dirty |= BM_VERT;
617
618         /* sort by vertex coordinates added together */
619         qsort(verts, verts_len, sizeof(BMVert *), vergaverco);
620
621         /* Flag keep_verts */
622         if (keepvert) {
623                 BMO_slot_buffer_flag_enable(bm, op->slots_in, "keep_verts", BM_VERT, VERT_KEEP);
624         }
625
626         for (i = 0; i < verts_len; i++) {
627                 BMVert *v_check = verts[i];
628
629                 if (BMO_vert_flag_test(bm, v_check, VERT_DOUBLE | VERT_TARGET)) {
630                         continue;
631                 }
632
633                 for (j = i + 1; j < verts_len; j++) {
634                         BMVert *v_other = verts[j];
635
636                         /* a match has already been found, (we could check which is best, for now don't) */
637                         if (BMO_vert_flag_test(bm, v_other, VERT_DOUBLE | VERT_TARGET)) {
638                                 continue;
639                         }
640
641                         /* Compare sort values of the verts using 3x tolerance (allowing for the tolerance
642                          * on each of the three axes). This avoids the more expensive length comparison
643                          * for most vertex pairs. */
644                         if ((v_other->co[0] + v_other->co[1] + v_other->co[2]) -
645                             (v_check->co[0] + v_check->co[1] + v_check->co[2]) > dist3)
646                         {
647                                 break;
648                         }
649
650                         if (keepvert) {
651                                 if (BMO_vert_flag_test(bm, v_other, VERT_KEEP) == BMO_vert_flag_test(bm, v_check, VERT_KEEP))
652                                         continue;
653                         }
654
655                         if (compare_len_squared_v3v3(v_check->co, v_other->co, dist_sq)) {
656
657                                 /* If one vert is marked as keep, make sure it will be the target */
658                                 if (BMO_vert_flag_test(bm, v_other, VERT_KEEP)) {
659                                         SWAP(BMVert *, v_check, v_other);
660                                 }
661
662                                 BMO_vert_flag_enable(bm, v_other, VERT_DOUBLE);
663                                 BMO_vert_flag_enable(bm, v_check, VERT_TARGET);
664
665                                 BMO_slot_map_elem_insert(optarget, optarget_slot, v_other, v_check);
666                         }
667                 }
668         }
669
670         MEM_freeN(verts);
671 }
672
673 void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op)
674 {
675         BMOperator weldop;
676         BMOpSlot *slot_targetmap;
677
678         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
679         slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
680         bmesh_find_doubles_common(bm, op,
681                                   &weldop, slot_targetmap);
682         BMO_op_exec(bm, &weldop);
683         BMO_op_finish(bm, &weldop);
684 }
685
686
687 void bmo_find_doubles_exec(BMesh *bm, BMOperator *op)
688 {
689         BMOpSlot *slot_targetmap_out;
690         slot_targetmap_out = BMO_slot_get(op->slots_out, "targetmap.out");
691         bmesh_find_doubles_common(bm, op,
692                                   op, slot_targetmap_out);
693 }
694
695 void bmo_automerge_exec(BMesh *bm, BMOperator *op)
696 {
697         BMOperator findop, weldop;
698         BMIter viter;
699         BMVert *v;
700
701         /* The "verts" input sent to this op is the set of verts that
702          * can be merged away into any other verts. Mark all other verts
703          * as VERT_KEEP. */
704         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_IN);
705         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
706                 if (!BMO_vert_flag_test(bm, v, VERT_IN)) {
707                         BMO_vert_flag_enable(bm, v, VERT_KEEP);
708                 }
709         }
710
711         /* Search for doubles among all vertices, but only merge non-VERT_KEEP
712          * vertices into VERT_KEEP vertices. */
713         BMO_op_initf(bm, &findop, op->flag, "find_doubles verts=%av keep_verts=%fv", VERT_KEEP);
714         BMO_slot_copy(op,      slots_in, "dist",
715                       &findop, slots_in, "dist");
716         BMO_op_exec(bm, &findop);
717
718         /* weld the vertices */
719         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
720         BMO_slot_copy(&findop, slots_out, "targetmap.out",
721                       &weldop, slots_in,  "targetmap");
722         BMO_op_exec(bm, &weldop);
723
724         BMO_op_finish(bm, &findop);
725         BMO_op_finish(bm, &weldop);
726 }