code cleanup: make bmesh operator names more consistant since python has access to...
[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 /** \file blender/bmesh/operators/bmo_dissolve.c
24  *  \ingroup bmesh
25  */
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_array.h"
30 #include "BLI_math.h"
31
32 #include "bmesh.h"
33 #include "intern/bmesh_private.h"
34
35 #include "intern/bmesh_operators_private.h" /* own include */
36
37 #define FACE_MARK   1
38 #define FACE_ORIG   2
39 #define FACE_NEW    4
40 #define EDGE_MARK   1
41
42 #define VERT_MARK   1
43
44 static int UNUSED_FUNCTION(check_hole_in_region) (BMesh * bm, BMFace * f)
45 {
46         BMWalker regwalker;
47         BMIter liter2;
48         BMLoop *l2, *l3;
49         BMFace *f2;
50
51         /* checks if there are any unmarked boundary edges in the face regio */
52
53         BMW_init(&regwalker, bm, BMW_ISLAND,
54                  BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
55                  BMW_FLAG_NOP,
56                  BMW_NIL_LAY);
57
58         f2 = BMW_begin(&regwalker, f);
59         for ( ; f2; f2 = BMW_step(&regwalker)) {
60                 l2 = BM_iter_new(&liter2, bm, BM_LOOPS_OF_FACE, f2);
61                 for ( ; l2; l2 = BM_iter_step(&liter2)) {
62                         l3 = l2->radial_next;
63                         if (BMO_elem_flag_test(bm, l3->f, FACE_MARK) !=
64                             BMO_elem_flag_test(bm, l2->f, FACE_MARK))
65                         {
66                                 if (!BMO_elem_flag_test(bm, l2->e, EDGE_MARK)) {
67                                         return FALSE;
68                                 }
69                         }
70                 }
71         }
72         BMW_end(&regwalker);
73
74         return TRUE;
75 }
76
77 void bmo_dissolve_faces_exec(BMesh *bm, BMOperator *op)
78 {
79         BMOIter oiter;
80         BMFace *f, *f2 /* , *nf = NULL */;
81         BLI_array_declare(faces);
82         BLI_array_declare(regions);
83         BMFace ***regions = NULL;
84         BMFace **faces = NULL;
85         BMWalker regwalker;
86         int i;
87
88         int use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
89
90         if (use_verts) {
91                 /* tag verts that start out with only 2 edges,
92                  * don't remove these later */
93                 BMIter viter;
94                 BMVert *v;
95
96                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
97                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
98                 }
99         }
100
101         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_MARK);
102         
103         /* collect region */
104         BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
105
106                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) {
107                         continue;
108                 }
109
110                 BLI_array_empty(faces);
111                 faces = NULL; /* forces different allocatio */
112
113                 BMW_init(&regwalker, bm, BMW_ISLAND,
114                          BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
115                          BMW_FLAG_NOP, /* no need to check BMW_FLAG_TEST_HIDDEN, faces are already marked by the bmo */
116                          BMW_NIL_LAY);
117
118                 f2 = BMW_begin(&regwalker, f);
119                 for ( ; f2; f2 = BMW_step(&regwalker)) {
120                         BLI_array_append(faces, f2);
121                 }
122                 BMW_end(&regwalker);
123                 
124                 for (i = 0; i < BLI_array_count(faces); i++) {
125                         f2 = faces[i];
126                         BMO_elem_flag_disable(bm, f2, FACE_MARK);
127                         BMO_elem_flag_enable(bm, f2, FACE_ORIG);
128                 }
129
130                 if (BMO_error_occurred(bm)) {
131                         BMO_error_clear(bm);
132                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
133                         goto cleanup;
134                 }
135                 
136                 BLI_array_append(faces, NULL);
137                 BLI_array_append(regions, faces);
138         }
139         
140         for (i = 0; i < BLI_array_count(regions); i++) {
141                 int tot = 0;
142                 
143                 faces = regions[i];
144                 if (!faces[0]) {
145                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
146                                         "Could not find boundary of dissolve region");
147                         goto cleanup;
148                 }
149                 
150                 while (faces[tot])
151                         tot++;
152                 
153                 f = BM_faces_join(bm, faces, tot, TRUE);
154                 if (!f) {
155                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
156                                         "Could not create merged face");
157                         goto cleanup;
158                 }
159
160                 /* if making the new face failed (e.g. overlapping test)
161                  * unmark the original faces for deletion */
162                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
163                 BMO_elem_flag_enable(bm, f, FACE_NEW);
164
165         }
166
167         BMO_op_callf(bm, op->flag, "delete geom=%ff context=%i", FACE_ORIG, DEL_FACES);
168
169
170         if (use_verts) {
171                 BMIter viter;
172                 BMVert *v;
173
174                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
175                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
176                                 if (BM_vert_edge_count(v) == 2) {
177                                         BM_vert_collapse_edge(bm, v->e, v, TRUE);
178                                 }
179                         }
180                 }
181         }
182
183         if (BMO_error_occurred(bm)) {
184                 goto cleanup;
185         }
186
187         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "region.out", BM_FACE, FACE_NEW);
188
189 cleanup:
190         /* free/cleanup */
191         for (i = 0; i < BLI_array_count(regions); i++) {
192                 if (regions[i]) MEM_freeN(regions[i]);
193         }
194
195         BLI_array_free(regions);
196 }
197
198 /* almost identical to dissolve edge, except it cleans up vertice */
199 void bmo_dissolve_edgeloop_exec(BMesh *bm, BMOperator *op)
200 {
201         /* BMOperator fop; */
202         BMOIter oiter;
203         BMIter iter;
204         BMVert *v, **verts = NULL;
205         BLI_array_declare(verts);
206         BMEdge *e;
207         BMFace *fa, *fb;
208         int i;
209
210
211         BMO_ITER (e, &oiter, op->slots_in, "edges", BM_EDGE) {
212                 if (BM_edge_face_pair(e, &fa, &fb)) {
213                         BMO_elem_flag_enable(bm, e->v1, VERT_MARK);
214                         BMO_elem_flag_enable(bm, e->v2, VERT_MARK);
215
216                         /* BMESH_TODO - check on delaying edge removal since we may end up removing more then
217                          * one edge, and later reference a removed edge */
218                         BM_faces_join_pair(bm, fa, fb, e, TRUE);
219                 }
220         }
221
222         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
223                 if (BMO_elem_flag_test(bm, v, VERT_MARK) && BM_vert_edge_count(v) == 2) {
224                         BLI_array_append(verts, v);
225                 }
226         }
227
228         /* clean up extreneous 2-valence vertice */
229         for (i = 0; i < BLI_array_count(verts); i++) {
230                 if (verts[i]->e) {
231                         BM_vert_collapse_edge(bm, verts[i]->e, verts[i], TRUE);
232                 }
233         }
234         
235         BLI_array_free(verts);
236
237         //BMO_op_initf(bm, &fop, "dissolve_faces faces=%ff", FACE_MARK);
238         //BMO_op_exec(bm, &fop);
239
240         //BMO_slot_copy(op, &fop, "region.out", "region.out");
241
242         //BMO_op_finish(bm, &fop);
243 }
244
245
246 void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op)
247 {
248         /* might want to make this an option or mode - campbell */
249
250         /* BMOperator fop; */
251         BMOIter eiter;
252         BMEdge *e;
253
254         BMIter viter;
255         BMVert *v;
256
257         int use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
258
259         if (use_verts) {
260                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
261                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
262                 }
263         }
264
265         BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
266                 BMFace *fa, *fb;
267
268                 if (BM_edge_face_pair(e, &fa, &fb)) {
269
270                         /* join faces */
271
272                         /* BMESH_TODO - check on delaying edge removal since we may end up removing more then
273                          * one edge, and later reference a removed edge */
274                         BM_faces_join_pair(bm, fa, fb, e, TRUE);
275                 }
276         }
277
278         if (use_verts) {
279                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
280                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
281                                 if (BM_vert_edge_count(v) == 2) {
282                                         BM_vert_collapse_edge(bm, v->e, v, TRUE);
283                                 }
284                         }
285                 }
286         }
287 }
288
289 static int test_extra_verts(BMesh *bm, BMVert *v)
290 {
291         BMIter iter, liter, iter2, iter3;
292         BMFace *f, *f2;
293         BMLoop *l;
294         BMEdge *e;
295         int found;
296
297         /* test faces around verts for verts that would be wrongly killed
298          * by dissolve faces. */
299         f = BM_iter_new(&iter, bm, BM_FACES_OF_VERT, v);
300         for ( ; f; f = BM_iter_step(&iter)) {
301                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
302                 for ( ; l; l = BM_iter_step(&liter)) {
303                         if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) {
304                                 /* if an edge around a vert is a boundary edge,
305                                  * then dissolve faces won't destroy it.
306                                  * also if it forms a boundary with one
307                                  * of the face region */
308                                 found = FALSE;
309                                 e = BM_iter_new(&iter2, bm, BM_EDGES_OF_VERT, l->v);
310                                 for ( ; e; e = BM_iter_step(&iter2)) {
311                                         if (BM_edge_is_boundary(e)) {
312                                                 found = TRUE;
313                                         }
314                                         f2 = BM_iter_new(&iter3, bm, BM_FACES_OF_EDGE, e);
315                                         for ( ; f2; f2 = BM_iter_step(&iter3)) {
316                                                 if (!BMO_elem_flag_test(bm, f2, FACE_MARK)) {
317                                                         found = TRUE;
318                                                         break;
319                                                 }
320                                         }
321                                         if (found == TRUE) {
322                                                 break;
323                                         }
324                                 }
325                                 if (found == FALSE) {
326                                         return FALSE;
327                                 }
328                         }
329                 }
330         }
331
332         return TRUE;
333 }
334 void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
335 {
336         BMIter iter, fiter;
337         BMVert *v;
338         BMFace *f;
339         /* int i; */
340
341         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_MARK);
342         
343         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
344                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
345                         /* check if it's a two-valence ver */
346                         if (BM_vert_edge_count(v) == 2) {
347
348                                 /* collapse the ver */
349                                 /* previously the faces were joined, but collapsing between 2 edges
350                                  * gives some advantage/difference in using vertex-dissolve over edge-dissolve */
351 #if 0
352                                 BM_vert_collapse_faces(bm, v->e, v, 1.0f, TRUE, TRUE);
353 #else
354                                 BM_vert_collapse_edge(bm, v->e, v, TRUE);
355 #endif
356
357                                 continue;
358                         }
359
360                         f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
361                         for ( ; f; f = BM_iter_step(&fiter)) {
362                                 BMO_elem_flag_enable(bm, f, FACE_ORIG);
363                                 BMO_elem_flag_enable(bm, f, FACE_MARK);
364                         }
365                         
366                         /* check if our additions to the input to face dissolve
367                          * will destroy nonmarked vertices. */
368                         if (!test_extra_verts(bm, v)) {
369                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
370                                 for ( ; f; f = BM_iter_step(&fiter)) {
371                                         if (BMO_elem_flag_test(bm, f, FACE_ORIG)) {
372                                                 BMO_elem_flag_disable(bm, f, FACE_MARK);
373                                                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
374                                         }
375                                 }
376                         }
377                         else {
378                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
379                                 for ( ; f; f = BM_iter_step(&fiter)) {
380                                         BMO_elem_flag_disable(bm, f, FACE_ORIG);
381                                 }
382                         }
383                 }
384         }
385
386         BMO_op_callf(bm, op->flag, "dissolve_faces faces=%ff", FACE_MARK);
387         if (BMO_error_occurred(bm)) {
388                 const char *msg;
389
390                 BMO_error_get(bm, &msg, NULL);
391                 BMO_error_clear(bm);
392                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg);
393         }
394         
395         /* clean up any remainin */
396         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
397                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
398                         if (!BM_vert_dissolve(bm, v)) {
399                                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
400                                 return;
401                         }
402                 }
403         }
404
405 }
406
407 /* this code is for cleaning up two-edged faces, it shall become
408  * it's own function one day */
409 #if 0
410 void dummy_exec(BMesh *bm, BMOperator *op)
411 {
412         {
413                 /* clean up two-edged face */
414                 /* basic idea is to keep joining 2-edged faces until their
415                  * gone.  this however relies on joining two 2-edged faces
416                  * together to work, which doesn't */
417                 found3 = 1;
418                 while (found3) {
419                         found3 = 0;
420                         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
421                                 if (!BM_face_validate(bm, f, stderr)) {
422                                         printf("error.\n");
423                                 }
424
425                                 if (f->len == 2) {
426                                         //this design relies on join faces working
427                                         //with two-edged faces properly.
428                                         //commenting this line disables the
429                                         //outermost loop.
430                                         //found3 = 1;
431                                         found2 = 0;
432                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
433                                         fe = l->e;
434                                         for ( ; l; l = BM_iter_step(&liter)) {
435                                                 f2 = BM_iter_new(&fiter, bm,
436                                                                  BM_FACES_OF_EDGE, l->e);
437                                                 for (; f2; f2 = BM_iter_step(&fiter)) {
438                                                         if (f2 != f) {
439                                                                 BM_faces_join_pair(bm, f, f2, l->e);
440                                                                 found2 = 1;
441                                                                 break;
442                                                         }
443                                                 }
444                                                 if (found2) break;
445                                         }
446
447                                         if (!found2) {
448                                                 BM_face_kill(bm, f);
449                                                 BM_edge_kill(bm, fe);
450                                         }
451                                 }
452 #if 0
453                                 else if (f->len == 3) {
454                                         BMEdge *ed[3];
455                                         BMVert *vt[3];
456                                         BMLoop *lp[3];
457                                         int i = 0;
458
459                                         //check for duplicate edges
460                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
461                                         for ( ; l; l = BM_iter_step(&liter)) {
462                                                 ed[i] = l->e;
463                                                 lp[i] = l;
464                                                 vt[i++] = l->v;
465                                         }
466                                         if (vt[0] == vt[1] || vt[0] == vt[2]) {
467                                                 i += 1;
468                                         }
469 #endif
470                         }
471                 }
472                 if (oldlen == len) break;
473                 oldlen = len;
474         }
475 }
476
477 #endif
478
479 /* Limited Dissolve */
480 void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
481 {
482         BMOpSlot *einput = BMO_slot_get(op->slots_in, "edges");
483         BMOpSlot *vinput = BMO_slot_get(op->slots_in, "verts");
484         const float angle_max = (float)M_PI / 2.0f;
485         const float angle_limit = min_ff(angle_max, BMO_slot_float_get(op->slots_in, "angle_limit"));
486         const int do_dissolve_boundaries = BMO_slot_bool_get(op->slots_in, "use_dissolve_boundaries");
487
488         BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries,
489                                      (BMVert **)BMO_SLOT_AS_BUFFER(vinput), vinput->len,
490                                      (BMEdge **)BMO_SLOT_AS_BUFFER(einput), einput->len);
491 }