d3c7a6864c33550cfede53c80955a529768e8bfd
[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  * Removes isolated geometry regions without creating holes in the mesh.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_array.h"
32 #include "BLI_math.h"
33
34 #include "bmesh.h"
35 #include "bmesh_tools.h"
36
37 #include "intern/bmesh_operators_private.h"
38
39
40 #define FACE_MARK   1
41 #define FACE_ORIG   2
42 #define FACE_NEW    4
43 #define EDGE_MARK   1
44 #define EDGE_TAG    2
45
46 #define VERT_MARK   1
47 #define VERT_TAG    2
48
49 static bool UNUSED_FUNCTION(check_hole_in_region) (BMesh *bm, BMFace *f)
50 {
51         BMWalker regwalker;
52         BMIter liter2;
53         BMLoop *l2, *l3;
54         BMFace *f2;
55
56         /* checks if there are any unmarked boundary edges in the face regio */
57
58         BMW_init(&regwalker, bm, BMW_ISLAND,
59                  BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
60                  BMW_FLAG_NOP,
61                  BMW_NIL_LAY);
62
63         for (f2 = BMW_begin(&regwalker, f); f2; f2 = BMW_step(&regwalker)) {
64                 BM_ITER_ELEM (l2, &liter2, f2, BM_LOOPS_OF_FACE) {
65                         l3 = l2->radial_next;
66                         if (BMO_elem_flag_test(bm, l3->f, FACE_MARK) !=
67                             BMO_elem_flag_test(bm, l2->f, FACE_MARK))
68                         {
69                                 if (!BMO_elem_flag_test(bm, l2->e, EDGE_MARK)) {
70                                         return false;
71                                 }
72                         }
73                 }
74         }
75         BMW_end(&regwalker);
76
77         return true;
78 }
79
80 static void bm_face_split(BMesh *bm, const short oflag)
81 {
82         BMIter iter;
83         BMVert *v;
84
85         BMIter liter;
86         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
87                 if (BMO_elem_flag_test(bm, v, oflag)) {
88                         if (BM_vert_edge_count(v) > 2) {
89                                 BMLoop *l;
90                                 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
91                                         if (l->f->len > 3) {
92                                                 if (BMO_elem_flag_test(bm, l->next->v, oflag) == 0 &&
93                                                     BMO_elem_flag_test(bm, l->prev->v, oflag) == 0)
94                                                 {
95                                                         BM_face_split(bm, l->f, l->next->v, l->prev->v, NULL, NULL, true);
96                                                 }
97                                         }
98                                 }
99                         }
100                 }
101         }
102 }
103
104 void bmo_dissolve_faces_exec(BMesh *bm, BMOperator *op)
105 {
106         BMOIter oiter;
107         BMFace *f;
108         BMFace ***regions = NULL;
109         BMFace **faces = NULL;
110         BLI_array_declare(regions);
111         BLI_array_declare(faces);
112         BMFace *act_face = bm->act_face;
113         BMWalker regwalker;
114         int i;
115
116         const bool use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
117
118         if (use_verts) {
119                 /* tag verts that start out with only 2 edges,
120                  * don't remove these later */
121                 BMIter viter;
122                 BMVert *v;
123
124                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
125                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
126                 }
127         }
128
129         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_MARK);
130         
131         /* collect region */
132         BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
133                 BMFace *f_iter;
134                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) {
135                         continue;
136                 }
137
138                 BLI_array_empty(faces);
139                 faces = NULL; /* forces different allocatio */
140
141                 BMW_init(&regwalker, bm, BMW_ISLAND,
142                          BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
143                          BMW_FLAG_NOP, /* no need to check BMW_FLAG_TEST_HIDDEN, faces are already marked by the bmo */
144                          BMW_NIL_LAY);
145
146                 for (f_iter = BMW_begin(&regwalker, f); f_iter; f_iter = BMW_step(&regwalker)) {
147                         BLI_array_append(faces, f_iter);
148                 }
149                 BMW_end(&regwalker);
150                 
151                 for (i = 0; i < BLI_array_count(faces); i++) {
152                         f_iter = faces[i];
153                         BMO_elem_flag_disable(bm, f_iter, FACE_MARK);
154                         BMO_elem_flag_enable(bm, f_iter, FACE_ORIG);
155                 }
156
157                 if (BMO_error_occurred(bm)) {
158                         BMO_error_clear(bm);
159                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
160                         goto cleanup;
161                 }
162                 
163                 BLI_array_append(faces, NULL);
164                 BLI_array_append(regions, faces);
165         }
166         
167         for (i = 0; i < BLI_array_count(regions); i++) {
168                 BMFace *f_new;
169                 int tot = 0;
170                 
171                 faces = regions[i];
172                 if (!faces[0]) {
173                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
174                                         "Could not find boundary of dissolve region");
175                         goto cleanup;
176                 }
177                 
178                 while (faces[tot])
179                         tot++;
180                 
181                 f_new = BM_faces_join(bm, faces, tot, true);
182
183                 if (f_new) {
184                         /* maintain active face */
185                         if (act_face && bm->act_face == NULL) {
186                                 bm->act_face = f_new;
187                         }
188                 }
189                 else {
190                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
191                                         "Could not create merged face");
192                         goto cleanup;
193                 }
194
195                 /* if making the new face failed (e.g. overlapping test)
196                  * unmark the original faces for deletion */
197                 BMO_elem_flag_disable(bm, f_new, FACE_ORIG);
198                 BMO_elem_flag_enable(bm, f_new, FACE_NEW);
199
200         }
201
202         BMO_op_callf(bm, op->flag, "delete geom=%ff context=%i", FACE_ORIG, DEL_FACES);
203
204
205         if (use_verts) {
206                 BMIter viter;
207                 BMVert *v;
208
209                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
210                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
211                                 if (BM_vert_edge_count(v) == 2) {
212                                         BM_vert_collapse_edge(bm, v->e, v, true);
213                                 }
214                         }
215                 }
216         }
217
218         if (BMO_error_occurred(bm)) {
219                 goto cleanup;
220         }
221
222         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "region.out", BM_FACE, FACE_NEW);
223
224 cleanup:
225         /* free/cleanup */
226         for (i = 0; i < BLI_array_count(regions); i++) {
227                 if (regions[i]) MEM_freeN(regions[i]);
228         }
229
230         BLI_array_free(regions);
231 }
232
233 void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op)
234 {
235         /* might want to make this an option or mode - campbell */
236
237         /* BMOperator fop; */
238         BMFace *act_face = bm->act_face;
239         BMOIter eiter;
240         BMEdge *e;
241         BMIter viter;
242         BMVert *v;
243
244         const bool use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
245         const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
246
247         if (use_face_split) {
248                 BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_TAG);
249
250                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
251                         BMIter iter;
252                         int untag_count = 0;
253                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
254                                 if (!BMO_elem_flag_test(bm, e, EDGE_TAG)) {
255                                         untag_count++;
256                                 }
257                         }
258
259                         /* check that we have 2 edges remaining after dissolve */
260                         if (untag_count <= 2) {
261                                 BMO_elem_flag_enable(bm, v, VERT_TAG);
262                         }
263                 }
264
265                 bm_face_split(bm, VERT_TAG);
266         }
267
268         if (use_verts) {
269                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
270                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
271                 }
272         }
273
274         BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
275                 BMFace *fa, *fb;
276
277                 if (BM_edge_face_pair(e, &fa, &fb)) {
278                         BMFace *f_new;
279
280                         /* join faces */
281
282                         /* BMESH_TODO - check on delaying edge removal since we may end up removing more than
283                          * one edge, and later reference a removed edge */
284                         f_new = BM_faces_join_pair(bm, fa, fb, e, true);
285
286                         if (f_new) {
287                                 /* maintain active face */
288                                 if (act_face && bm->act_face == NULL) {
289                                         bm->act_face = f_new;
290                                 }
291                         }
292                 }
293         }
294
295         if (use_verts) {
296                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
297                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
298                                 if (BM_vert_edge_count(v) == 2) {
299                                         BM_vert_collapse_edge(bm, v->e, v, true);
300                                 }
301                         }
302                 }
303         }
304 }
305
306 static bool test_extra_verts(BMesh *bm, BMVert *v)
307 {
308         BMIter fiter, liter, eiter, fiter_sub;
309         BMFace *f;
310         BMLoop *l;
311         BMEdge *e;
312
313         /* test faces around verts for verts that would be wrongly killed
314          * by dissolve faces. */
315         BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
316                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
317                         if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) {
318                                 /* if an edge around a vert is a boundary edge,
319                                  * then dissolve faces won't destroy it.
320                                  * also if it forms a boundary with one
321                                  * of the face region */
322                                 bool found = false;
323                                 BM_ITER_ELEM (e, &eiter, l->v, BM_EDGES_OF_VERT) {
324                                         BMFace *f_iter;
325                                         if (BM_edge_is_boundary(e)) {
326                                                 found = true;
327                                         }
328                                         else {
329                                                 BM_ITER_ELEM (f_iter, &fiter_sub, e, BM_FACES_OF_EDGE) {
330                                                         if (!BMO_elem_flag_test(bm, f_iter, FACE_MARK)) {
331                                                                 found = true;
332                                                                 break;
333                                                         }
334                                                 }
335                                         }
336                                         if (found == true) {
337                                                 break;
338                                         }
339                                 }
340                                 if (found == false) {
341                                         return false;
342                                 }
343                         }
344                 }
345         }
346
347         return true;
348 }
349 void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
350 {
351         BMIter iter, fiter;
352         BMVert *v;
353         BMFace *f;
354
355         const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
356
357
358         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_MARK);
359         
360         if (use_face_split) {
361                 bm_face_split(bm, VERT_MARK);
362         }
363
364         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
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                         BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
382                                 BMO_elem_flag_enable(bm, f, FACE_MARK | FACE_ORIG);
383                         }
384                         
385                         /* check if our additions to the input to face dissolve
386                          * will destroy nonmarked vertices. */
387                         if (!test_extra_verts(bm, v)) {
388                                 BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
389                                         if (BMO_elem_flag_test(bm, f, FACE_ORIG)) {
390                                                 BMO_elem_flag_disable(bm, f, FACE_MARK | FACE_ORIG);
391                                         }
392                                 }
393                         }
394                         else {
395                                 BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
396                                         BMO_elem_flag_disable(bm, f, FACE_ORIG);
397                                 }
398                         }
399                 }
400         }
401
402         BMO_op_callf(bm, op->flag, "dissolve_faces faces=%ff", FACE_MARK);
403         if (BMO_error_occurred(bm)) {
404                 const char *msg;
405
406                 BMO_error_get(bm, &msg, NULL);
407                 BMO_error_clear(bm);
408                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg);
409         }
410         
411         /* clean up any remainin */
412         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
413                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
414                         if (!BM_vert_dissolve(bm, v)) {
415                                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
416                                 return;
417                         }
418                 }
419         }
420
421 }
422
423 /* Limited Dissolve */
424 void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
425 {
426         BMOpSlot *einput = BMO_slot_get(op->slots_in, "edges");
427         BMOpSlot *vinput = BMO_slot_get(op->slots_in, "verts");
428         const float angle_max = (float)M_PI / 2.0f;
429         const float angle_limit = min_ff(angle_max, BMO_slot_float_get(op->slots_in, "angle_limit"));
430         const bool do_dissolve_boundaries = BMO_slot_bool_get(op->slots_in, "use_dissolve_boundaries");
431         const BMO_Delimit delimit = BMO_slot_int_get(op->slots_in, "delimit");
432
433         BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries, delimit,
434                                      (BMVert **)BMO_SLOT_AS_BUFFER(vinput), vinput->len,
435                                      (BMEdge **)BMO_SLOT_AS_BUFFER(einput), einput->len,
436                                      FACE_NEW);
437
438         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "region.out", BM_FACE, FACE_NEW);
439 }