bebfeaa5b0603fb7caeaf3364a695f17d6aa96d2
[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 /* ***_ISGC: mark for garbage-collection */
41
42 #define FACE_MARK   1
43 #define FACE_ORIG   2
44 #define FACE_NEW    4
45
46 #define EDGE_MARK   1
47 #define EDGE_TAG    2
48 #define EDGE_ISGC   8
49
50 #define VERT_MARK   1
51 #define VERT_TAG    2
52 #define VERT_ISGC   8
53
54
55
56 static bool UNUSED_FUNCTION(check_hole_in_region) (BMesh *bm, BMFace *f)
57 {
58         BMWalker regwalker;
59         BMIter liter2;
60         BMLoop *l2, *l3;
61         BMFace *f2;
62
63         /* checks if there are any unmarked boundary edges in the face regio */
64
65         BMW_init(&regwalker, bm, BMW_ISLAND,
66                  BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
67                  BMW_FLAG_NOP,
68                  BMW_NIL_LAY);
69
70         for (f2 = BMW_begin(&regwalker, f); f2; f2 = BMW_step(&regwalker)) {
71                 BM_ITER_ELEM (l2, &liter2, f2, BM_LOOPS_OF_FACE) {
72                         l3 = l2->radial_next;
73                         if (BMO_elem_flag_test(bm, l3->f, FACE_MARK) !=
74                             BMO_elem_flag_test(bm, l2->f, FACE_MARK))
75                         {
76                                 if (!BMO_elem_flag_test(bm, l2->e, EDGE_MARK)) {
77                                         return false;
78                                 }
79                         }
80                 }
81         }
82         BMW_end(&regwalker);
83
84         return true;
85 }
86
87 static void bm_face_split(BMesh *bm, const short oflag)
88 {
89         BMIter iter;
90         BMVert *v;
91
92         BMIter liter;
93         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
94                 if (BMO_elem_flag_test(bm, v, oflag)) {
95                         if (BM_vert_is_edge_pair(v) == false) {
96                                 BMLoop *l;
97                                 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
98                                         if (l->f->len > 3) {
99                                                 if (BMO_elem_flag_test(bm, l->next->v, oflag) == 0 &&
100                                                     BMO_elem_flag_test(bm, l->prev->v, oflag) == 0)
101                                                 {
102                                                         BM_face_split(bm, l->f, l->next, l->prev, NULL, NULL, true);
103                                                 }
104                                         }
105                                 }
106                         }
107                 }
108         }
109 }
110
111 void bmo_dissolve_faces_exec(BMesh *bm, BMOperator *op)
112 {
113         BMOIter oiter;
114         BMFace *f;
115         BMFace ***regions = NULL;
116         BMFace **faces = NULL;
117         BLI_array_declare(regions);
118         BLI_array_declare(faces);
119         BMFace *act_face = bm->act_face;
120         BMWalker regwalker;
121         int i;
122
123         const bool use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
124
125         if (use_verts) {
126                 /* tag verts that start out with only 2 edges,
127                  * don't remove these later */
128                 BMIter viter;
129                 BMVert *v;
130
131                 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
132                         BMO_elem_flag_set(bm, v, VERT_MARK, !BM_vert_is_edge_pair(v));
133                 }
134         }
135
136         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_MARK);
137         
138         /* collect region */
139         BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
140                 BMFace *f_iter;
141                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) {
142                         continue;
143                 }
144
145                 BLI_array_empty(faces);
146                 faces = NULL; /* forces different allocatio */
147
148                 BMW_init(&regwalker, bm, BMW_ISLAND,
149                          BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
150                          BMW_FLAG_NOP, /* no need to check BMW_FLAG_TEST_HIDDEN, faces are already marked by the bmo */
151                          BMW_NIL_LAY);
152
153                 for (f_iter = BMW_begin(&regwalker, f); f_iter; f_iter = BMW_step(&regwalker)) {
154                         BLI_array_append(faces, f_iter);
155                 }
156                 BMW_end(&regwalker);
157                 
158                 for (i = 0; i < BLI_array_count(faces); i++) {
159                         f_iter = faces[i];
160                         BMO_elem_flag_disable(bm, f_iter, FACE_MARK);
161                         BMO_elem_flag_enable(bm, f_iter, FACE_ORIG);
162                 }
163
164                 if (BMO_error_occurred(bm)) {
165                         BMO_error_clear(bm);
166                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
167                         goto cleanup;
168                 }
169                 
170                 BLI_array_append(faces, NULL);
171                 BLI_array_append(regions, faces);
172         }
173         
174         for (i = 0; i < BLI_array_count(regions); i++) {
175                 BMFace *f_new;
176                 int tot = 0;
177                 
178                 faces = regions[i];
179                 if (!faces[0]) {
180                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
181                                         "Could not find boundary of dissolve region");
182                         goto cleanup;
183                 }
184                 
185                 while (faces[tot])
186                         tot++;
187                 
188                 f_new = BM_faces_join(bm, faces, tot, true);
189
190                 if (f_new) {
191                         /* maintain active face */
192                         if (act_face && bm->act_face == NULL) {
193                                 bm->act_face = f_new;
194                         }
195                 }
196                 else {
197                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
198                                         "Could not create merged face");
199                         goto cleanup;
200                 }
201
202                 /* if making the new face failed (e.g. overlapping test)
203                  * unmark the original faces for deletion */
204                 BMO_elem_flag_disable(bm, f_new, FACE_ORIG);
205                 BMO_elem_flag_enable(bm, f_new, FACE_NEW);
206
207         }
208
209         BMO_op_callf(bm, op->flag, "delete geom=%ff context=%i", FACE_ORIG, DEL_FACES);
210
211
212         if (use_verts) {
213                 BMIter viter;
214                 BMVert *v, *v_next;
215
216                 BM_ITER_MESH_MUTABLE (v, v_next, &viter, bm, BM_VERTS_OF_MESH) {
217                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
218                                 if (BM_vert_is_edge_pair(v)) {
219                                         BM_vert_collapse_edge(bm, v->e, v, true, true);
220                                 }
221                         }
222                 }
223         }
224
225         if (BMO_error_occurred(bm)) {
226                 goto cleanup;
227         }
228
229         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "region.out", BM_FACE, FACE_NEW);
230
231 cleanup:
232         /* free/cleanup */
233         for (i = 0; i < BLI_array_count(regions); i++) {
234                 if (regions[i]) MEM_freeN(regions[i]);
235         }
236
237         BLI_array_free(regions);
238 }
239
240 void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op)
241 {
242         /* BMOperator fop; */
243         BMFace *act_face = bm->act_face;
244         BMOIter eiter;
245         BMIter iter;
246         BMEdge *e, *e_next;
247         BMVert *v, *v_next;
248
249         const bool use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
250         const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
251
252         if (use_face_split) {
253                 BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_TAG);
254
255                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
256                         BMIter itersub;
257                         int untag_count = 0;
258                         BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
259                                 if (!BMO_elem_flag_test(bm, e, EDGE_TAG)) {
260                                         untag_count++;
261                                 }
262                         }
263
264                         /* check that we have 2 edges remaining after dissolve */
265                         if (untag_count <= 2) {
266                                 BMO_elem_flag_enable(bm, v, VERT_TAG);
267                         }
268                 }
269
270                 bm_face_split(bm, VERT_TAG);
271         }
272
273         if (use_verts) {
274                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
275                         BMO_elem_flag_set(bm, v, VERT_MARK, !BM_vert_is_edge_pair(v));
276                 }
277         }
278
279         /* tag all verts/edges connected to faces */
280         BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
281                 BMFace *f_pair[2];
282                 if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
283                         unsigned int j;
284                         for (j = 0; j < 2; j++) {
285                                 BMLoop *l_first, *l_iter;
286                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_pair[j]);
287                                 do {
288                                         BMO_elem_flag_enable(bm, l_iter->v, VERT_ISGC);
289                                         BMO_elem_flag_enable(bm, l_iter->e, EDGE_ISGC);
290                                 } while ((l_iter = l_iter->next) != l_first);
291                         }
292                 }
293         }
294
295         BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
296                 BMFace *fa, *fb;
297                 if (BM_edge_face_pair(e, &fa, &fb)) {
298                         BMFace *f_new;
299
300                         /* join faces */
301                         f_new = BM_faces_join_pair(bm, fa, fb, e, false);
302
303                         if (f_new) {
304                                 /* maintain active face */
305                                 if (act_face && bm->act_face == NULL) {
306                                         bm->act_face = f_new;
307                                 }
308                         }
309                 }
310         }
311
312         /* Cleanup geometry (#BM_faces_join_pair, but it removes geometry we're looping on)
313          * so do this in a separate pass instead. */
314         BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
315                 if ((e->l == NULL) && BMO_elem_flag_test(bm, e, EDGE_ISGC)) {
316                         BM_edge_kill(bm, e);
317                 }
318         }
319         BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
320                 if ((v->e == NULL) && BMO_elem_flag_test(bm, v, VERT_ISGC)) {
321                         BM_vert_kill(bm, v);
322                 }
323         }
324         /* done with cleanup */
325
326
327         if (use_verts) {
328                 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
329                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
330                                 if (BM_vert_is_edge_pair(v)) {
331                                         BM_vert_collapse_edge(bm, v->e, v, true, true);
332                                 }
333                         }
334                 }
335         }
336 }
337
338 void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
339 {
340         BMOIter oiter;
341         BMIter iter;
342         BMVert *v, *v_next;
343         BMEdge *e, *e_next;
344         BMFace *act_face = bm->act_face;
345
346         const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
347
348         BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
349                 BMIter itersub;
350
351                 BMO_elem_flag_enable(bm, v, VERT_MARK | VERT_ISGC);
352
353                 BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
354                         BMO_elem_flag_enable(bm, e, EDGE_ISGC);
355                 }
356         }
357
358         if (use_face_split) {
359                 bm_face_split(bm, VERT_MARK);
360         }
361
362         BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
363                 BMIter itersub;
364                 BMLoop *l_first;
365                 BM_ITER_ELEM (l_first, &itersub, v, BM_LOOPS_OF_VERT) {
366                         BMLoop *l_iter;
367                         l_iter = l_first;
368                         do {
369                                 BMO_elem_flag_enable(bm, l_iter->v, VERT_ISGC);
370                                 BMO_elem_flag_enable(bm, l_iter->e, EDGE_ISGC);
371                         } while ((l_iter = l_iter->next) != l_first);
372                 }
373         }
374
375         BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
376                 BMIter itersub;
377
378                 if (BM_vert_edge_count(v) != 2) {
379                         BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
380                                 BMFace *fa, *fb;
381                                 if (BM_edge_face_pair(e, &fa, &fb)) {
382                                         BMFace *f_new;
383
384                                         /* join faces */
385                                         f_new = BM_faces_join_pair(bm, fa, fb, e, false);
386
387                                         /* maintain active face */
388                                         if (act_face && bm->act_face == NULL) {
389                                                 bm->act_face = f_new;
390                                         }
391                                 }
392                         }
393                 }
394         }
395
396         /* Cleanup geometry (#BM_faces_join_pair, but it removes geometry we're looping on)
397          * so do this in a separate pass instead. */
398         BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
399                 if ((e->l == NULL) && BMO_elem_flag_test(bm, e, EDGE_ISGC)) {
400                         BM_edge_kill(bm, e);
401                 }
402         }
403         BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
404                 if ((v->e == NULL) && BMO_elem_flag_test(bm, v, VERT_ISGC)) {
405                         BM_vert_kill(bm, v);
406                 }
407         }
408         /* done with cleanup */
409
410         BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
411                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
412                         if (BM_vert_edge_count(v) == 2) {
413                                 BM_vert_collapse_edge(bm, v->e, v, true, true);
414                         }
415                 }
416         }
417 }
418
419 /* Limited Dissolve */
420 void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
421 {
422         BMOpSlot *einput = BMO_slot_get(op->slots_in, "edges");
423         BMOpSlot *vinput = BMO_slot_get(op->slots_in, "verts");
424         const float angle_max = (float)M_PI / 2.0f;
425         const float angle_limit = min_ff(angle_max, BMO_slot_float_get(op->slots_in, "angle_limit"));
426         const bool do_dissolve_boundaries = BMO_slot_bool_get(op->slots_in, "use_dissolve_boundaries");
427         const BMO_Delimit delimit = BMO_slot_int_get(op->slots_in, "delimit");
428
429         BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries, delimit,
430                                      (BMVert **)BMO_SLOT_AS_BUFFER(vinput), vinput->len,
431                                      (BMEdge **)BMO_SLOT_AS_BUFFER(einput), einput->len,
432                                      FACE_NEW);
433
434         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "region.out", BM_FACE, FACE_NEW);
435 }
436
437
438 #define EDGE_MARK 1
439 #define EDGE_COLLAPSE 2
440
441 static void bm_mesh_edge_collapse_flagged(BMesh *bm, const int flag, const short oflag)
442 {
443         BMO_op_callf(bm, flag, "collapse edges=%fe", oflag);
444 }
445
446 void bmo_dissolve_degenerate_exec(BMesh *bm, BMOperator *op)
447 {
448         const float dist = BMO_slot_float_get(op->slots_in, "dist");
449         const float dist_sq = dist * dist;
450
451         bool found;
452         BMIter eiter;
453         BMEdge *e;
454
455
456         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
457
458         /* collapse zero length edges, this accounts for zero area faces too */
459         found = false;
460         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
461                 if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
462                         if (BM_edge_calc_length_squared(e) < dist_sq) {
463                                 BMO_elem_flag_enable(bm, e, EDGE_COLLAPSE);
464                                 found = true;
465                         }
466                 }
467
468                 /* clear all loop tags (checked later) */
469                 if (e->l) {
470                         BMLoop *l_iter, *l_first;
471                         l_iter = l_first = e->l;
472                         do {
473                                 BM_elem_flag_disable(l_iter, BM_ELEM_TAG);
474                         } while ((l_iter = l_iter->radial_next) != l_first);
475                 }
476         }
477
478         if (found) {
479                 bm_mesh_edge_collapse_flagged(bm, op->flag, EDGE_COLLAPSE);
480         }
481
482
483         /* clip degenerate ears from the face */
484         found = false;
485         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
486                 if (e->l && BMO_elem_flag_test(bm, e, EDGE_MARK)) {
487                         BMLoop *l_iter, *l_first;
488                         l_iter = l_first = e->l;
489                         do {
490                                 if (
491                                     /* check the loop hasn't already been tested (and flag not to test again) */
492                                     !BM_elem_flag_test(l_iter, BM_ELEM_TAG) &&
493                                     (BM_elem_flag_enable(l_iter, BM_ELEM_TAG),
494
495                                      /* check we're marked to tested (radial edge already tested) */
496                                      BMO_elem_flag_test(bm, l_iter->prev->e, EDGE_MARK) &&
497
498                                      /* check edges are not already going to be collapsed */
499                                      !BMO_elem_flag_test(bm, l_iter->e, EDGE_COLLAPSE) &&
500                                      !BMO_elem_flag_test(bm, l_iter->prev->e, EDGE_COLLAPSE)))
501                                 {
502                                         /* test if the faces loop (ear) is degenerate */
503                                         float dir_prev[3], len_prev;
504                                         float dir_next[3], len_next;
505
506
507                                         sub_v3_v3v3(dir_prev, l_iter->prev->v->co, l_iter->v->co);
508                                         sub_v3_v3v3(dir_next, l_iter->next->v->co, l_iter->v->co);
509
510                                         len_prev = normalize_v3(dir_prev);
511                                         len_next = normalize_v3(dir_next);
512
513                                         if ((len_v3v3(dir_prev, dir_next) * min_ff(len_prev, len_next)) <= dist) {
514                                                 bool reset = false;
515
516                                                 if (fabsf(len_prev - len_next) <= dist) {
517                                                         /* both edges the same length */
518                                                         if (l_iter->f->len == 3) {
519                                                                 /* ideally this would have been discovered with short edge test above */
520                                                                 BMO_elem_flag_enable(bm, l_iter->next->e, EDGE_COLLAPSE);
521                                                                 found = true;
522                                                         }
523                                                         else {
524                                                                 /* add a joining edge and tag for removal */
525                                                                 BMLoop *l_split;
526                                                                 if (BM_face_split(bm, l_iter->f, l_iter->prev, l_iter->next, &l_split, NULL, true)) {
527                                                                         BMO_elem_flag_enable(bm, l_split->e, EDGE_COLLAPSE);
528                                                                         found = true;
529                                                                         reset = true;
530                                                                 }
531                                                         }
532                                                 }
533                                                 else if (len_prev < len_next) {
534                                                         /* split 'l_iter->e', then join the vert with next */
535                                                         BMVert *v_new;
536                                                         BMEdge *e_new;
537                                                         BMLoop *l_split;
538                                                         v_new = BM_edge_split(bm, l_iter->e, l_iter->v, &e_new, len_prev / len_next);
539                                                         BLI_assert(v_new == l_iter->next->v);
540                                                         (void)v_new;
541                                                         if (BM_face_split(bm, l_iter->f, l_iter->prev, l_iter->next, &l_split, NULL, true)) {
542                                                                 BMO_elem_flag_enable(bm, l_split->e, EDGE_COLLAPSE);
543                                                                 found = true;
544                                                         }
545                                                         reset = true;
546                                                 }
547                                                 else if (len_next < len_prev) {
548                                                         /* split 'l_iter->prev->e', then join the vert with next */
549                                                         BMVert *v_new;
550                                                         BMEdge *e_new;
551                                                         BMLoop *l_split;
552                                                         v_new = BM_edge_split(bm, l_iter->prev->e, l_iter->v, &e_new, len_next / len_prev);
553                                                         BLI_assert(v_new == l_iter->prev->v);
554                                                         (void)v_new;
555                                                         if (BM_face_split(bm, l_iter->f, l_iter->prev, l_iter->next, &l_split, NULL, true)) {
556                                                                 BMO_elem_flag_enable(bm, l_split->e, EDGE_COLLAPSE);
557                                                                 found = true;
558                                                         }
559                                                         reset = true;
560                                                 }
561
562                                                 if (reset) {
563                                                         /* we can't easily track where we are on the radial edge, reset! */
564                                                         l_first = l_iter;
565                                                 }
566                                         }
567                                 }
568                         } while ((l_iter = l_iter->radial_next) != l_first);
569                 }
570         }
571
572         if (found) {
573                 bm_mesh_edge_collapse_flagged(bm, op->flag, EDGE_COLLAPSE);
574         }
575
576 }