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