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