fix [#36923] Merge / Delete vertices crashes for some meshes
[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                 BMVert *v_next;
297                 BM_ITER_MESH_MUTABLE (v, v_next, &viter, bm, BM_VERTS_OF_MESH) {
298                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
299                                 if (BM_vert_edge_count(v) == 2) {
300                                         BM_vert_collapse_edge(bm, v->e, v, true);
301                                 }
302                         }
303                 }
304         }
305 }
306
307 static bool test_extra_verts(BMesh *bm, BMVert *v)
308 {
309         BMIter fiter, liter, eiter, fiter_sub;
310         BMFace *f;
311         BMLoop *l;
312         BMEdge *e;
313
314         /* test faces around verts for verts that would be wrongly killed
315          * by dissolve faces. */
316         BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
317                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
318                         if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) {
319                                 /* if an edge around a vert is a boundary edge,
320                                  * then dissolve faces won't destroy it.
321                                  * also if it forms a boundary with one
322                                  * of the face region */
323                                 bool found = false;
324                                 BM_ITER_ELEM (e, &eiter, l->v, BM_EDGES_OF_VERT) {
325                                         BMFace *f_iter;
326                                         if (BM_edge_is_boundary(e)) {
327                                                 found = true;
328                                         }
329                                         else {
330                                                 BM_ITER_ELEM (f_iter, &fiter_sub, e, BM_FACES_OF_EDGE) {
331                                                         if (!BMO_elem_flag_test(bm, f_iter, FACE_MARK)) {
332                                                                 found = true;
333                                                                 break;
334                                                         }
335                                                 }
336                                         }
337                                         if (found == true) {
338                                                 break;
339                                         }
340                                 }
341                                 if (found == false) {
342                                         return false;
343                                 }
344                         }
345                 }
346         }
347
348         return true;
349 }
350 void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
351 {
352         BMIter iter, fiter;
353         BMVert *v, *v_next;
354         BMFace *f;
355
356         const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
357
358
359         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_MARK);
360         
361         if (use_face_split) {
362                 bm_face_split(bm, VERT_MARK);
363         }
364
365         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
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                         BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
383                                 BMO_elem_flag_enable(bm, f, FACE_MARK | FACE_ORIG);
384                         }
385                         
386                         /* check if our additions to the input to face dissolve
387                          * will destroy nonmarked vertices. */
388                         if (!test_extra_verts(bm, v)) {
389                                 BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
390                                         if (BMO_elem_flag_test(bm, f, FACE_ORIG)) {
391                                                 BMO_elem_flag_disable(bm, f, FACE_MARK | FACE_ORIG);
392                                         }
393                                 }
394                         }
395                         else {
396                                 BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
397                                         BMO_elem_flag_disable(bm, f, FACE_ORIG);
398                                 }
399                         }
400                 }
401         }
402
403         BMO_op_callf(bm, op->flag, "dissolve_faces faces=%ff", FACE_MARK);
404         if (BMO_error_occurred(bm)) {
405                 const char *msg;
406
407                 BMO_error_get(bm, &msg, NULL);
408                 BMO_error_clear(bm);
409                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg);
410         }
411         
412         /* clean up any remainin */
413         BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
414                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
415                         if (!BM_vert_dissolve(bm, v)) {
416                                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
417                                 return;
418                         }
419                 }
420         }
421
422 }
423
424 /* Limited Dissolve */
425 void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
426 {
427         BMOpSlot *einput = BMO_slot_get(op->slots_in, "edges");
428         BMOpSlot *vinput = BMO_slot_get(op->slots_in, "verts");
429         const float angle_max = (float)M_PI / 2.0f;
430         const float angle_limit = min_ff(angle_max, BMO_slot_float_get(op->slots_in, "angle_limit"));
431         const bool do_dissolve_boundaries = BMO_slot_bool_get(op->slots_in, "use_dissolve_boundaries");
432         const BMO_Delimit delimit = BMO_slot_int_get(op->slots_in, "delimit");
433
434         BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries, delimit,
435                                      (BMVert **)BMO_SLOT_AS_BUFFER(vinput), vinput->len,
436                                      (BMEdge **)BMO_SLOT_AS_BUFFER(einput), einput->len,
437                                      FACE_NEW);
438
439         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "region.out", BM_FACE, FACE_NEW);
440 }