code cleanup: make bmesh operator names more consistant since python has access to...
[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
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_math.h"
30 #include "BLI_array.h"
31
32 #include "BKE_customdata.h"
33
34 #include "bmesh.h"
35 #include "intern/bmesh_private.h"
36
37 #include "intern/bmesh_operators_private.h" /* own include */
38
39 static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op)
40 {
41         BMIter liter;
42         BMLoop *l;
43         BMVert *v2, *doub;
44         int split = FALSE;
45
46         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
47                 v2 = BMO_slot_map_ptr_get(op->slots_in, "targetmap", l->v);
48                 /* ok: if v2 is NULL (e.g. not in the map) then it's
49                  *     a target vert, otherwise it's a double */
50                 if ((v2 && BM_vert_in_face(f, v2)) &&
51                     (v2 != l->prev->v) &&
52                     (v2 != l->next->v))
53                 {
54                         doub = l->v;
55                         split = TRUE;
56                         break;
57                 }
58         }
59
60         if (split && doub != v2) {
61                 BMLoop *nl;
62                 BMFace *f2 = BM_face_split(bm, f, doub, v2, &nl, NULL, FALSE);
63
64                 remdoubles_splitface(f, bm, op);
65                 remdoubles_splitface(f2, bm, op);
66         }
67 }
68
69 #define ELE_DEL         1
70 #define EDGE_COL        2
71 #define FACE_MARK       2
72
73 #if 0
74 int remdoubles_face_overlaps(BMesh *bm, BMVert **varr,
75                              int len, BMFace *exclude,
76                              BMFace **overlapface)
77 {
78         BMIter vertfaces;
79         BMFace *f;
80         int i, amount;
81
82         if (overlapface) *overlapface = NULL;
83
84         for (i = 0; i < len; i++) {
85                 f = BM_iter_new(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]);
86                 while (f) {
87                         amount = BM_verts_in_face(bm, f, varr, len);
88                         if (amount >= len) {
89                                 if (overlapface) *overlapface = f;
90                                 return TRUE;
91                         }
92                         f = BM_iter_step(&vertfaces);
93                 }
94         }
95         return FALSE;
96 }
97 #endif
98
99 void bmo_weld_verts_exec(BMesh *bm, BMOperator *op)
100 {
101         BMIter iter, liter;
102         BMVert *v, *v2;
103         BMEdge *e, *e2, **edges = NULL;
104         BLI_array_declare(edges);
105         BMLoop *l, *l2, **loops = NULL;
106         BLI_array_declare(loops);
107         BMFace *f, *f2;
108         int a, b;
109
110         /* mark merge verts for deletion */
111         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
112                 if ((v2 = BMO_slot_map_ptr_get(op->slots_in, "targetmap", v))) {
113                         BMO_elem_flag_enable(bm, v, ELE_DEL);
114
115                         /* merge the vertex flags, else we get randomly selected/unselected verts */
116                         BM_elem_flag_merge(v, v2);
117                 }
118         }
119
120         /* check if any faces are getting their own corners merged
121          * together, split face if so */
122         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
123                 remdoubles_splitface(f, bm, op);
124         }
125
126         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
127                 if (BMO_elem_flag_test(bm, e->v1, ELE_DEL) || BMO_elem_flag_test(bm, e->v2, ELE_DEL)) {
128                         v  = BMO_slot_map_ptr_get(op->slots_in, "targetmap", e->v1);
129                         v2 = BMO_slot_map_ptr_get(op->slots_in, "targetmap", e->v2);
130                         
131                         if (!v) v = e->v1;
132                         if (!v2) v2 = e->v2;
133
134                         if (v == v2) {
135                                 BMO_elem_flag_enable(bm, e, EDGE_COL);
136                         }
137                         else if (!BM_edge_exists(v, v2)) {
138                                 BM_edge_create(bm, v, v2, e, TRUE);
139                         }
140
141                         BMO_elem_flag_enable(bm, e, ELE_DEL);
142                 }
143         }
144
145         /* BMESH_TODO, stop abusing face index here */
146         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
147                 BM_elem_index_set(f, 0); /* set_dirty! */
148                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
149                         if (BMO_elem_flag_test(bm, l->v, ELE_DEL)) {
150                                 BMO_elem_flag_enable(bm, f, FACE_MARK | ELE_DEL);
151                         }
152                         if (BMO_elem_flag_test(bm, l->e, EDGE_COL)) {
153                                 BM_elem_index_set(f, BM_elem_index_get(f) + 1); /* set_dirty! */
154                         }
155                 }
156         }
157         bm->elem_index_dirty |= BM_FACE;
158
159         /* faces get "modified" by creating new faces here, then at the
160          * end the old faces are deleted */
161         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
162                 if (!BMO_elem_flag_test(bm, f, FACE_MARK))
163                         continue;
164
165                 if (f->len - BM_elem_index_get(f) < 3) {
166                         BMO_elem_flag_enable(bm, f, ELE_DEL);
167                         continue;
168                 }
169
170                 BLI_array_empty(edges);
171                 BLI_array_empty(loops);
172                 a = 0;
173                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
174                         v = l->v;
175                         v2 = l->next->v;
176                         if (BMO_elem_flag_test(bm, v, ELE_DEL)) {
177                                 v = BMO_slot_map_ptr_get(op->slots_in, "targetmap", v);
178                         }
179                         if (BMO_elem_flag_test(bm, v2, ELE_DEL)) {
180                                 v2 = BMO_slot_map_ptr_get(op->slots_in, "targetmap", v2);
181                         }
182                         
183                         e2 = v != v2 ? BM_edge_exists(v, v2) : NULL;
184                         if (e2) {
185                                 for (b = 0; b < a; b++) {
186                                         if (edges[b] == e2) {
187                                                 break;
188                                         }
189                                 }
190                                 if (b != a) {
191                                         continue;
192                                 }
193
194                                 BLI_array_grow_one(edges);
195                                 BLI_array_grow_one(loops);
196
197                                 edges[a] = e2;
198                                 loops[a] = l;
199
200                                 a++;
201                         }
202                 }
203                 
204                 if (BLI_array_count(loops) < 3)
205                         continue;
206                 v = loops[0]->v;
207                 v2 = loops[1]->v;
208
209                 if (BMO_elem_flag_test(bm, v, ELE_DEL)) {
210                         v = BMO_slot_map_ptr_get(op->slots_in, "targetmap", v);
211                 }
212                 if (BMO_elem_flag_test(bm, v2, ELE_DEL)) {
213                         v2 = BMO_slot_map_ptr_get(op->slots_in, "targetmap", v2);
214                 }
215                 
216                 f2 = BM_face_create_ngon(bm, v, v2, edges, a, TRUE);
217                 if (f2 && (f2 != f)) {
218                         BM_elem_attrs_copy(bm, bm, f, f2);
219
220                         a = 0;
221                         BM_ITER_ELEM (l, &liter, f2, BM_LOOPS_OF_FACE) {
222                                 l2 = loops[a];
223                                 BM_elem_attrs_copy(bm, bm, l2, l);
224
225                                 a++;
226                         }
227                 }
228         }
229
230         BMO_op_callf(bm, op->flag, "delete geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
231
232         BLI_array_free(edges);
233         BLI_array_free(loops);
234 }
235
236 static int vergaverco(const void *e1, const void *e2)
237 {
238         const BMVert *v1 = *(void **)e1, *v2 = *(void **)e2;
239         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
240         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
241
242         if      (x1 > x2) return  1;
243         else if (x1 < x2) return -1;
244         else return 0;
245 }
246
247 // #define VERT_TESTED  1 // UNUSED
248 #define VERT_DOUBLE     2
249 #define VERT_TARGET     4
250 #define VERT_KEEP       8
251 // #define VERT_MARK    16 // UNUSED
252 #define VERT_IN         32
253
254 #define EDGE_MARK       1
255
256 void bmo_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
257 {
258         BMOIter siter;
259         BMIter iter;
260         BMVert *v, *snapv;
261         BMLoop *l, *firstl = NULL;
262         float fac;
263         int i, tot;
264
265         snapv = BMO_iter_new(&siter, op->slots_in, "snapv", BM_VERT);
266         tot = BM_vert_face_count(snapv);
267
268         if (!tot)
269                 return;
270
271         fac = 1.0f / tot;
272         BM_ITER_ELEM (l, &iter, snapv, BM_LOOPS_OF_VERT) {
273                 if (!firstl) {
274                         firstl = l;
275                 }
276                 
277                 for (i = 0; i < bm->ldata.totlayer; i++) {
278                         if (CustomData_layer_has_math(&bm->ldata, i)) {
279                                 int type = bm->ldata.layers[i].type;
280                                 void *e1, *e2;
281
282                                 e1 = CustomData_bmesh_get_layer_n(&bm->ldata, firstl->head.data, i);
283                                 e2 = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
284                                 
285                                 CustomData_data_multiply(type, e2, fac);
286
287                                 if (l != firstl)
288                                         CustomData_data_add(type, e1, e2);
289                         }
290                 }
291         }
292
293         BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
294                 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
295                         if (l == firstl) {
296                                 continue;
297                         }
298
299                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, firstl->head.data, &l->head.data);
300                 }
301         }
302 }
303
304 void bmo_average_vert_facedata_exec(BMesh *bm, BMOperator *op)
305 {
306         BMOIter siter;
307         BMIter iter;
308         BMVert *v;
309         BMLoop *l /* , *firstl = NULL */;
310         CDBlockBytes min, max;
311         void *block;
312         int i, type;
313
314         for (i = 0; i < bm->ldata.totlayer; i++) {
315                 if (!CustomData_layer_has_math(&bm->ldata, i))
316                         continue;
317                 
318                 type = bm->ldata.layers[i].type;
319                 CustomData_data_initminmax(type, &min, &max);
320
321                 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
322                         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
323                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
324                                 CustomData_data_dominmax(type, block, &min, &max);
325                         }
326                 }
327
328                 CustomData_data_multiply(type, &min, 0.5f);
329                 CustomData_data_multiply(type, &max, 0.5f);
330                 CustomData_data_add(type, &min, &max);
331
332                 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
333                         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
334                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
335                                 CustomData_data_copy_value(type, &min, block);
336                         }
337                 }
338         }
339 }
340
341 void bmo_pointmerge_exec(BMesh *bm, BMOperator *op)
342 {
343         BMOperator weldop;
344         BMOIter siter;
345         BMVert *v, *snapv = NULL;
346         float vec[3];
347         
348         BMO_slot_vec_get(op->slots_in, "merge_co", vec);
349
350         //BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
351         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
352         
353         BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
354                 if (!snapv) {
355                         snapv = v;
356                         copy_v3_v3(snapv->co, vec);
357                 }
358                 else {
359                         BMO_slot_map_ptr_insert(&weldop, weldop.slots_in, "targetmap", v, snapv);
360                 }
361         }
362
363         BMO_op_exec(bm, &weldop);
364         BMO_op_finish(bm, &weldop);
365 }
366
367 void bmo_collapse_exec(BMesh *bm, BMOperator *op)
368 {
369         BMOperator weldop;
370         BMWalker walker;
371         BMIter iter;
372         BMEdge *e, **edges = NULL;
373         BLI_array_declare(edges);
374         float min[3], max[3], center[3];
375         int i, tot;
376         
377         BMO_op_callf(bm, op->flag, "collapse_uvs edges=%s", op, "edges");
378         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
379
380         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
381
382         BMW_init(&walker, bm, BMW_SHELL,
383                  BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP,
384                  BMW_FLAG_NOP, /* no need to use BMW_FLAG_TEST_HIDDEN, already marked data */
385                  BMW_NIL_LAY);
386
387         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
388                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK))
389                         continue;
390
391                 e = BMW_begin(&walker, e->v1);
392                 BLI_array_empty(edges);
393
394                 INIT_MINMAX(min, max);
395                 for (tot = 0; e; tot++, e = BMW_step(&walker)) {
396                         BLI_array_grow_one(edges);
397                         edges[tot] = e;
398
399                         minmax_v3v3_v3(min, max, e->v1->co);
400                         minmax_v3v3_v3(min, max, e->v2->co);
401                 }
402
403                 mid_v3_v3v3(center, min, max);
404
405                 /* snap edges to a point.  for initial testing purposes anyway */
406                 for (i = 0; i < tot; i++) {
407                         copy_v3_v3(edges[i]->v1->co, center);
408                         copy_v3_v3(edges[i]->v2->co, center);
409                         
410                         if (edges[i]->v1 != edges[0]->v1)
411                                 BMO_slot_map_ptr_insert(&weldop, weldop.slots_in, "targetmap", edges[i]->v1, edges[0]->v1);
412                         if (edges[i]->v2 != edges[0]->v1)
413                                 BMO_slot_map_ptr_insert(&weldop, weldop.slots_in, "targetmap", edges[i]->v2, edges[0]->v1);
414                 }
415         }
416         
417         BMO_op_exec(bm, &weldop);
418         BMO_op_finish(bm, &weldop);
419
420         BMW_end(&walker);
421         BLI_array_free(edges);
422 }
423
424 /* uv collapse function */
425 static void bmo_collapsecon_do_layer(BMesh *bm, BMOperator *op, int layer)
426 {
427         BMIter iter, liter;
428         BMFace *f;
429         BMLoop *l, *l2;
430         BMWalker walker;
431         void **blocks = NULL;
432         BLI_array_declare(blocks);
433         CDBlockBytes min, max;
434         int i, tot, type = bm->ldata.layers[layer].type;
435
436         /* clear all short flags */
437         BMO_mesh_flag_disable_all(bm, op, BM_ALL, (1 << 16) - 1);
438
439         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
440
441         BMW_init(&walker, bm, BMW_LOOPDATA_ISLAND,
442                  BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP,
443                  BMW_FLAG_NOP, /* no need to use BMW_FLAG_TEST_HIDDEN, already marked data */
444                  layer);
445
446         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
447                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
448                         if (BMO_elem_flag_test(bm, l->e, EDGE_MARK)) {
449                                 /* walk */
450                                 BLI_array_empty(blocks);
451                                 tot = 0;
452                                 l2 = BMW_begin(&walker, l);
453
454                                 CustomData_data_initminmax(type, &min, &max);
455                                 for (tot = 0; l2; tot++, l2 = BMW_step(&walker)) {
456                                         BLI_array_grow_one(blocks);
457                                         blocks[tot] = CustomData_bmesh_get_layer_n(&bm->ldata, l2->head.data, layer);
458                                         CustomData_data_dominmax(type, blocks[tot], &min, &max);
459                                 }
460
461                                 if (tot) {
462                                         CustomData_data_multiply(type, &min, 0.5f);
463                                         CustomData_data_multiply(type, &max, 0.5f);
464                                         CustomData_data_add(type, &min, &max);
465
466                                         /* snap CD (uv, vcol) points to their centroid */
467                                         for (i = 0; i < tot; i++) {
468                                                 CustomData_data_copy_value(type, &min, blocks[i]);
469                                         }
470                                 }
471                         }
472                 }
473         }
474
475         BMW_end(&walker);
476         BLI_array_free(blocks);
477 }
478
479 void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op)
480 {
481         int i;
482
483         for (i = 0; i < bm->ldata.totlayer; i++) {
484                 if (CustomData_layer_has_math(&bm->ldata, i))
485                         bmo_collapsecon_do_layer(bm, op, i);
486         }
487 }
488
489 static void bmesh_find_doubles_common(BMesh *bm, BMOperator *op,
490                                       BMOperator *optarget,
491                                       BMOpSlot optarget_slot_args[BMO_OP_MAX_SLOTS],
492                                       const char *targetmapname)
493 {
494         BMVert  **verts;
495         int       verts_len;
496
497         int i, j, keepvert = 0;
498
499         const float dist  = BMO_slot_float_get(op->slots_in, "dist");
500         const float dist3 = dist * 3.0f;
501
502         /* Test whether keep_verts arg exists and is non-empty */
503         if (BMO_slot_exists(op->slots_in, "keep_verts")) {
504                 BMOIter oiter;
505                 keepvert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL;
506         }
507
508         /* get the verts as an array we can sort */
509         verts = BMO_slot_as_arrayN(op->slots_in, "verts", &verts_len);
510
511         /* sort by vertex coordinates added together */
512         qsort(verts, verts_len, sizeof(BMVert *), vergaverco);
513
514         /* Flag keep_verts */
515         if (keepvert) {
516                 BMO_slot_buffer_flag_enable(bm, op->slots_in, "keep_verts", BM_VERT, VERT_KEEP);
517         }
518
519         for (i = 0; i < verts_len; i++) {
520                 BMVert *v_check = verts[i];
521
522                 if (BMO_elem_flag_test(bm, v_check, VERT_DOUBLE)) {
523                         continue;
524                 }
525
526                 for (j = i + 1; j < verts_len; j++) {
527                         BMVert *v_other = verts[j];
528
529                         /* Compare sort values of the verts using 3x tolerance (allowing for the tolerance
530                          * on each of the three axes). This avoids the more expensive length comparison
531                          * for most vertex pairs. */
532                         if ((v_other->co[0] + v_other->co[1] + v_other->co[2]) -
533                             (v_check->co[0] + v_check->co[1] + v_check->co[2]) > dist3)
534                         {
535                                 break;
536                         }
537
538                         if (keepvert) {
539                                 if (BMO_elem_flag_test(bm, v_other, VERT_KEEP) == BMO_elem_flag_test(bm, v_check, VERT_KEEP))
540                                         continue;
541                         }
542
543                         if (compare_len_v3v3(v_check->co, v_other->co, dist)) {
544
545                                 /* If one vert is marked as keep, make sure it will be the target */
546                                 if (BMO_elem_flag_test(bm, v_other, VERT_KEEP)) {
547                                         SWAP(BMVert *, v_check, v_other);
548                                 }
549
550                                 BMO_elem_flag_enable(bm, v_other, VERT_DOUBLE);
551                                 BMO_elem_flag_enable(bm, v_check, VERT_TARGET);
552
553                                 BMO_slot_map_ptr_insert(optarget, optarget_slot_args, targetmapname, v_other, v_check);
554                         }
555                 }
556         }
557
558         MEM_freeN(verts);
559 }
560
561 void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op)
562 {
563         BMOperator weldop;
564
565         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
566         bmesh_find_doubles_common(bm, op,
567                                   &weldop, weldop.slots_in, "targetmap");
568         BMO_op_exec(bm, &weldop);
569         BMO_op_finish(bm, &weldop);
570 }
571
572
573 void bmo_find_doubles_exec(BMesh *bm, BMOperator *op)
574 {
575         bmesh_find_doubles_common(bm, op,
576                                   op, op->slots_out, "targetmap.out");
577 }
578
579 void bmo_automerge_exec(BMesh *bm, BMOperator *op)
580 {
581         BMOperator findop, weldop;
582         BMIter viter;
583         BMVert *v;
584
585         /* The "verts" input sent to this op is the set of verts that
586          * can be merged away into any other verts. Mark all other verts
587          * as VERT_KEEP. */
588         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_IN);
589         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
590                 if (!BMO_elem_flag_test(bm, v, VERT_IN)) {
591                         BMO_elem_flag_enable(bm, v, VERT_KEEP);
592                 }
593         }
594
595         /* Search for doubles among all vertices, but only merge non-VERT_KEEP
596          * vertices into VERT_KEEP vertices. */
597         BMO_op_initf(bm, &findop, op->flag, "find_doubles verts=%av keep_verts=%fv", VERT_KEEP);
598         BMO_slot_copy(op,      slots_in, "dist",
599                       &findop, slots_in, "dist");
600         BMO_op_exec(bm, &findop);
601
602         /* weld the vertices */
603         BMO_op_init(bm, &weldop, op->flag, "weld_verts");
604         BMO_slot_copy(&findop, slots_out, "targetmap.out",
605                       &weldop, slots_in,  "targetmap");
606         BMO_op_exec(bm, &weldop);
607
608         BMO_op_finish(bm, &findop);
609         BMO_op_finish(bm, &weldop);
610 }