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