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