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