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