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