added boolean type for bmesh operators, will make python wrapping clearer and also...
[blender.git] / source / blender / bmesh / operators / bmo_dissolve.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_array.h"
26 #include "BLI_math.h"
27
28 #include "bmesh.h"
29 #include "bmesh_private.h"
30
31 #include "bmesh_operators_private.h" /* own include */
32
33 #define FACE_MARK       1
34 #define FACE_ORIG       2
35 #define FACE_NEW        4
36 #define EDGE_MARK       1
37
38 #define VERT_MARK       1
39
40 static int UNUSED_FUNCTION(check_hole_in_region)(BMesh *bm, BMFace *f)
41 {
42         BMWalker regwalker;
43         BMIter liter2;
44         BMLoop *l2, *l3;
45         BMFace *f2;
46
47         /* checks if there are any unmarked boundary edges in the face regio */
48
49         BMW_init(&regwalker, bm, BMW_ISLAND,
50                  BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
51                  BMW_NIL_LAY);
52         f2 = BMW_begin(&regwalker, f);
53         for ( ; f2; f2 = BMW_step(&regwalker)) {
54                 l2 = BM_iter_new(&liter2, bm, BM_LOOPS_OF_FACE, f2);
55                 for ( ; l2; l2 = BM_iter_step(&liter2)) {
56                         l3 = bmesh_radial_nextloop(l2);
57                         if ( BMO_elem_flag_test(bm, l3->f, FACE_MARK) !=
58                              BMO_elem_flag_test(bm, l2->f, FACE_MARK))
59                         {
60                                 if (!BMO_elem_flag_test(bm, l2->e, EDGE_MARK)) {
61                                         return FALSE;
62                                 }
63                         }
64                 }
65         }
66         BMW_end(&regwalker);
67
68         return TRUE;
69 }
70
71 void dissolvefaces_exec(BMesh *bm, BMOperator *op)
72 {
73         BMOIter oiter;
74         BMFace *f, *f2 /* , *nf = NULL */;
75         BLI_array_declare(faces);
76         BLI_array_declare(regions);
77         BMFace ***regions = NULL;
78         BMFace **faces = NULL;
79         BMWalker regwalker;
80         int i;
81
82         int use_verts = BMO_slot_bool_get(op, "use_verts");
83
84         if (use_verts) {
85                 /* tag verts that start out with only 2 edges,
86                  * don't remove these later */
87                 BMIter viter;
88                 BMVert *v;
89
90                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
91                         if (BM_vert_edge_count(v) == 2) {
92                                 BMO_elem_flag_disable(bm, v, VERT_MARK);
93                         }
94                         else {
95                                 BMO_elem_flag_enable(bm, v, VERT_MARK);
96                         }
97                 }
98         }
99
100         BMO_slot_buffer_flag_enable(bm, op, "faces", FACE_MARK, BM_FACE);
101         
102         /* collect region */
103         BMO_ITER(f, &oiter, bm, op, "faces", BM_FACE) {
104                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) continue;
105
106                 BLI_array_empty(faces);
107                 faces = NULL; /* forces different allocatio */
108
109                 /* yay, walk */
110                 BMW_init(&regwalker, bm, BMW_ISLAND,
111                          BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
112                          BMW_NIL_LAY);
113
114                 f2 = BMW_begin(&regwalker, f);
115                 for ( ; f2; f2 = BMW_step(&regwalker)) {
116                         BLI_array_append(faces, f2);
117                 }
118                 BMW_end(&regwalker);
119                 
120                 for (i = 0; i < BLI_array_count(faces); i++) {
121                         f2 = faces[i];
122                         BMO_elem_flag_disable(bm, f2, FACE_MARK);
123                         BMO_elem_flag_enable(bm, f2, FACE_ORIG);
124                 }
125
126                 if (BMO_error_occurred(bm)) {
127                         BMO_error_clear(bm);
128                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
129                         goto cleanup;
130                 }
131                 
132                 BLI_array_append(faces, NULL);
133                 BLI_array_append(regions, faces);
134         }
135         
136         for (i = 0; i < BLI_array_count(regions); i++) {
137                 int tot = 0;
138                 
139                 faces = regions[i];
140                 if (!faces[0]) {
141                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
142                                         "Could not find boundary of dissolve region");
143                         goto cleanup;
144                 }
145                 
146                 while (faces[tot])
147                         tot++;
148                 
149                 f = BM_faces_join(bm, faces, tot);
150                 if (!f) {
151                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
152                                         "Could not create merged face");
153                         goto cleanup;
154                 }
155
156                 /* if making the new face failed (e.g. overlapping test)
157                  * unmark the original faces for deletion */
158                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
159                 BMO_elem_flag_enable(bm, f, FACE_NEW);
160
161         }
162
163         BMO_op_callf(bm, "del geom=%ff context=%i", FACE_ORIG, DEL_FACES);
164
165
166         if (use_verts) {
167                 BMIter viter;
168                 BMVert *v;
169
170                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
171                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
172                                 if (BM_vert_edge_count(v) == 2) {
173                                         BM_vert_collapse_edges(bm, v->e, v);
174                                 }
175                         }
176                 }
177         }
178
179         if (BMO_error_occurred(bm)) goto cleanup;
180
181         BMO_slot_from_flag(bm, op, "regionout", FACE_NEW, BM_FACE);
182
183 cleanup:
184         /* free/cleanu */
185         for (i = 0; i < BLI_array_count(regions); i++) {
186                 if (regions[i]) MEM_freeN(regions[i]);
187         }
188
189         BLI_array_free(regions);
190 }
191
192 /* almost identical to dissolve edge, except it cleans up vertice */
193 void dissolve_edgeloop_exec(BMesh *bm, BMOperator *op)
194 {
195         /* BMOperator fop; */
196         BMOIter oiter;
197         BMIter iter;
198         BMVert *v, **verts = NULL;
199         BLI_array_declare(verts);
200         BMEdge *e;
201         /* BMFace *f; */
202         int i;
203
204         BMO_ITER(e, &oiter, bm, op, "edges", BM_EDGE) {
205                 if (BM_edge_face_count(e) == 2) {
206                         BMO_elem_flag_enable(bm, e->v1, VERT_MARK);
207                         BMO_elem_flag_enable(bm, e->v2, VERT_MARK);
208
209                         BM_faces_join_pair(bm, e->l->f,
210                                            e->l->radial_next->f,
211                                            e);
212                 }
213         }
214
215         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
216                 if (BMO_elem_flag_test(bm, v, VERT_MARK) && BM_vert_edge_count(v) == 2) {
217                         BLI_array_append(verts, v);
218                 }
219         }
220
221         /* clean up extreneous 2-valence vertice */
222         for (i = 0; i < BLI_array_count(verts); i++) {
223                 if (verts[i]->e) {
224                         BM_vert_collapse_edges(bm, verts[i]->e, verts[i]);
225                 }
226         }
227         
228         BLI_array_free(verts);
229
230         //BMO_op_initf(bm, &fop, "dissolvefaces faces=%ff", FACE_MARK);
231         //BMO_op_exec(bm, &fop);
232
233         //BMO_slot_copy(op, &fop, "regionout", "regionout");
234
235         //BMO_op_finish(bm, &fop);
236 }
237
238
239 void dissolveedges_exec(BMesh *bm, BMOperator *op)
240 {
241         /* might want to make this an option or mode - campbell */
242
243         /* BMOperator fop; */
244         BMOIter eiter;
245         BMEdge *e;
246
247         BMIter viter;
248         BMVert *v;
249
250         int use_verts = BMO_slot_bool_get(op, "use_verts");
251
252         if (use_verts) {
253                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
254                         if (BM_vert_edge_count(v) == 2) {
255                                 BMO_elem_flag_disable(bm, v, VERT_MARK);
256                         }
257                         else {
258                                 BMO_elem_flag_enable(bm, v, VERT_MARK);
259                         }
260                 }
261         }
262
263         BMO_ITER(e, &eiter, bm, op, "edges", BM_EDGE) {
264                 const int edge_face_count = BM_edge_face_count(e);
265                 if (edge_face_count == 2) {
266
267                         /* join faces */
268                         BM_faces_join_pair(bm, e->l->f,
269                                            e->l->radial_next->f,
270                                            e);
271                 }
272         }
273
274         if (use_verts) {
275                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
276                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
277                                 if (BM_vert_edge_count(v) == 2) {
278                                         BM_vert_collapse_edges(bm, v->e, v);
279                                 }
280                         }
281                 }
282         }
283 }
284
285 static int test_extra_verts(BMesh *bm, BMVert *v)
286 {
287         BMIter iter, liter, iter2, iter3;
288         BMFace *f, *f2;
289         BMLoop *l;
290         BMEdge *e;
291         int found;
292
293         /* test faces around verts for verts that would be wronly killed
294          * by dissolve faces. */
295         f = BM_iter_new(&iter, bm, BM_FACES_OF_VERT, v);
296         for ( ; f; f = BM_iter_step(&iter)) {
297                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
298                 for ( ; l; l = BM_iter_step(&liter)) {
299                         if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) {
300                                 /* if an edge around a vert is a boundary edge,
301                                  * then dissolve faces won't destroy it.
302                                  * also if it forms a boundary with one
303                                  * of the face region */
304                                 found = FALSE;
305                                 e = BM_iter_new(&iter2, bm, BM_EDGES_OF_VERT, l->v);
306                                 for ( ; e; e = BM_iter_step(&iter2)) {
307                                         if (BM_edge_face_count(e) == 1) {
308                                                 found = TRUE;
309                                         }
310                                         f2 = BM_iter_new(&iter3, bm, BM_FACES_OF_EDGE, e);
311                                         for ( ; f2; f2 = BM_iter_step(&iter3)) {
312                                                 if (!BMO_elem_flag_test(bm, f2, FACE_MARK)) {
313                                                         found = TRUE;
314                                                         break;
315                                                 }
316                                         }
317                                         if (found == TRUE) {
318                                                 break;
319                                         }
320                                 }
321                                 if (found == FALSE) {
322                                         return FALSE;
323                                 }
324                         }
325                 }
326         }
327
328         return TRUE;
329 }
330 void dissolveverts_exec(BMesh *bm, BMOperator *op)
331 {
332         BMOpSlot *vinput;
333         BMIter iter, fiter;
334         BMVert *v;
335         BMFace *f;
336         /* int i; */
337         
338         vinput = BMO_slot_get(op, "verts");
339         BMO_slot_buffer_flag_enable(bm, op, "verts", VERT_MARK, BM_VERT);
340         
341         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
342                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
343                         /* check if it's a two-valence ver */
344                         if (BM_vert_edge_count(v) == 2) {
345
346                                 /* collapse the ver */
347                                 BM_vert_collapse_faces(bm, v->e, v, 1.0f, TRUE);
348                                 continue;
349                         }
350
351                         f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
352                         for ( ; f; f = BM_iter_step(&fiter)) {
353                                 BMO_elem_flag_enable(bm, f, FACE_ORIG);
354                                 BMO_elem_flag_enable(bm, f, FACE_MARK);
355                         }
356                         
357                         /* check if our additions to the input to face dissolve
358                          * will destroy nonmarked vertices. */
359                         if (!test_extra_verts(bm, v)) {
360                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
361                                 for ( ; f; f = BM_iter_step(&fiter)) {
362                                         if (BMO_elem_flag_test(bm, f, FACE_ORIG)) {
363                                                 BMO_elem_flag_disable(bm, f, FACE_MARK);
364                                                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
365                                         }
366                                 }
367                         }
368                         else {
369                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
370                                 for ( ; f; f = BM_iter_step(&fiter)) {
371                                         BMO_elem_flag_disable(bm, f, FACE_ORIG);
372                                 }
373                         }
374                 }
375         }
376
377         BMO_op_callf(bm, "dissolvefaces faces=%ff", FACE_MARK);
378         if (BMO_error_occurred(bm)) {
379                 const char *msg;
380
381                 BMO_error_get(bm, &msg, NULL);
382                 BMO_error_clear(bm);
383                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg);
384         }
385         
386         /* clean up any remainin */
387         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
388                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
389                         if (!BM_vert_dissolve(bm, v)) {
390                                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
391                                 return;
392                         }
393                 }
394         }
395
396 }
397
398 /* this code is for cleaning up two-edged faces, it shall become
399  * it's own function one day */
400 #if 0
401 void dummy_exec(BMesh *bm, BMOperator *op)
402 {
403         {
404                 /* clean up two-edged face */
405                 /* basic idea is to keep joining 2-edged faces until their
406                  * gone.  this however relies on joining two 2-edged faces
407                  * together to work, which doesn't */
408                 found3 = 1;
409                 while (found3) {
410                         found3 = 0;
411                         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
412                                 if (!BM_face_validate(bm, f, stderr)) {
413                                         printf("error.\n");
414                                 }
415
416                                 if (f->len == 2) {
417                                         //this design relies on join faces working
418                                         //with two-edged faces properly.
419                                         //commenting this line disables the
420                                         //outermost loop.
421                                         //found3 = 1;
422                                         found2 = 0;
423                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
424                                         fe = l->e;
425                                         for ( ; l; l = BM_iter_step(&liter)) {
426                                                 f2 = BM_iter_new(&fiter, bm,
427                                                                 BM_FACES_OF_EDGE, l->e);
428                                                 for ( ; f2; f2 = BM_iter_step(&fiter)) {
429                                                         if (f2 != f) {
430                                                                 BM_faces_join_pair(bm, f, f2, l->e);
431                                                                 found2 = 1;
432                                                                 break;
433                                                         }
434                                                 }
435                                                 if (found2) break;
436                                         }
437
438                                         if (!found2) {
439                                                 bmesh_kf(bm, f);
440                                                 bmesh_ke(bm, fe);
441                                         }
442                                 } /* else if (f->len == 3) {
443                                         BMEdge *ed[3];
444                                         BMVert *vt[3];
445                                         BMLoop *lp[3];
446                                         int i = 0;
447
448                                         //check for duplicate edges
449                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
450                                         for ( ; l; l = BM_iter_step(&liter)) {
451                                                 ed[i] = l->e;
452                                                 lp[i] = l;
453                                                 vt[i++] = l->v;
454                                         }
455                                         if (vt[0] == vt[1] || vt[0] == vt[2]) {
456                                                 i += 1;
457                                         }
458                                  */
459                         }
460                 }
461                 if (oldlen == len) break;
462                 oldlen = len;
463         }
464 }
465
466 #endif
467
468 /**/
469 typedef struct DissolveElemWeight_t {
470         BMHeader *ele;
471         float weight;
472 } DissolveElemWeight_t;
473
474 static int dissolve_elem_cmp(const void *a1, const void *a2)
475 {
476         const struct DissolveElemWeight_t *d1 = a1, *d2 = a2;
477
478         if      (d1->weight > d2->weight) return  1;
479         else if (d1->weight < d2->weight) return -1;
480         return 0;
481 }
482
483 void dissolvelimit_exec(BMesh *bm, BMOperator *op)
484 {
485         BMOpSlot *einput = BMO_slot_get(op, "edges");
486         BMOpSlot *vinput = BMO_slot_get(op, "verts");
487         const float angle_max = (float)M_PI / 2.0f;
488         const float angle_limit = minf(angle_max, BMO_slot_float_get(op, "angle_limit"));
489         DissolveElemWeight_t *weight_elems = MEM_mallocN(MAX2(einput->len, vinput->len) *
490                                                          sizeof(DissolveElemWeight_t), __func__);
491         int i, tot_found;
492
493         /* --- first edges --- */
494
495         /* go through and split edge */
496         for (i = 0, tot_found = 0; i < einput->len; i++) {
497                 BMEdge *e = ((BMEdge **)einput->data.p)[i];
498                 const float angle = BM_edge_face_angle(bm, e);
499
500                 if (angle < angle_limit) {
501                         weight_elems[i].ele = (BMHeader *)e;
502                         weight_elems[i].weight = angle;
503                         tot_found++;
504                 }
505                 else {
506                         weight_elems[i].ele = NULL;
507                         weight_elems[i].weight = angle_max;
508                 }
509         }
510
511         if (tot_found != 0) {
512                 qsort(weight_elems, einput->len, sizeof(DissolveElemWeight_t), dissolve_elem_cmp);
513
514                 for (i = 0; i < tot_found; i++) {
515                         BMEdge *e = (BMEdge *)weight_elems[i].ele;
516                         /* check twice because cumulative effect could disolve over angle limit */
517                         if (BM_edge_face_angle(bm, e) < angle_limit) {
518                                 BMFace *nf = BM_faces_join_pair(bm, e->l->f,
519                                                                 e->l->radial_next->f,
520                                                                 e); /* join faces */
521
522                                 /* there may be some errors, we dont mind, just move on */
523                                 if (nf == NULL) {
524                                         BMO_error_clear(bm);
525                                 }
526                         }
527                 }
528         }
529
530         /* --- second verts --- */
531         for (i = 0, tot_found = 0; i < vinput->len; i++) {
532                 BMVert *v = ((BMVert **)vinput->data.p)[i];
533                 const float angle = BM_vert_edge_angle(bm, v);
534
535                 if (angle < angle_limit) {
536                         weight_elems[i].ele = (BMHeader *)v;
537                         weight_elems[i].weight = angle;
538                         tot_found++;
539                 }
540                 else {
541                         weight_elems[i].ele = NULL;
542                         weight_elems[i].weight = angle_max;
543                 }
544         }
545
546         if (tot_found != 0) {
547                 qsort(weight_elems, vinput->len, sizeof(DissolveElemWeight_t), dissolve_elem_cmp);
548
549                 for (i = 0; i < tot_found; i++) {
550                         BMVert *v = (BMVert *)weight_elems[i].ele;
551                         /* check twice because cumulative effect could disolve over angle limit */
552                         if (BM_vert_edge_angle(bm, v) < angle_limit) {
553                                 BM_vert_collapse_edges(bm, v->e, v); /* join edges */
554                         }
555                 }
556         }
557
558         MEM_freeN(weight_elems);
559 }