Merged changes in the trunk up to revision 45431.
[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 #include "MEM_guardedalloc.h"
24
25 #include "BLI_array.h"
26 #include "BLI_math.h"
27
28 #include "bmesh.h"
29 #include "intern/bmesh_private.h"
30
31 #include "intern/bmesh_operators_private.h" /* own include */
32
33 #define FACE_MARK       1
34 #define FACE_ORIG       2
35 #define FACE_NEW        4
36 #define EDGE_MARK       1
37
38 #define VERT_MARK       1
39
40 static int UNUSED_FUNCTION(check_hole_in_region)(BMesh *bm, BMFace *f)
41 {
42         BMWalker regwalker;
43         BMIter liter2;
44         BMLoop *l2, *l3;
45         BMFace *f2;
46
47         /* checks if there are any unmarked boundary edges in the face regio */
48
49         BMW_init(&regwalker, bm, BMW_ISLAND,
50                  BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
51                  BMW_FLAG_NOP, /* BMESH_TODO - should be BMW_FLAG_TEST_HIDDEN ? */
52                  BMW_NIL_LAY);
53
54         f2 = BMW_begin(&regwalker, f);
55         for ( ; f2; f2 = BMW_step(&regwalker)) {
56                 l2 = BM_iter_new(&liter2, bm, BM_LOOPS_OF_FACE, f2);
57                 for ( ; l2; l2 = BM_iter_step(&liter2)) {
58                         l3 = l2->radial_next;
59                         if ( BMO_elem_flag_test(bm, l3->f, FACE_MARK) !=
60                              BMO_elem_flag_test(bm, l2->f, FACE_MARK))
61                         {
62                                 if (!BMO_elem_flag_test(bm, l2->e, EDGE_MARK)) {
63                                         return FALSE;
64                                 }
65                         }
66                 }
67         }
68         BMW_end(&regwalker);
69
70         return TRUE;
71 }
72
73 void bmo_dissolve_faces_exec(BMesh *bm, BMOperator *op)
74 {
75         BMOIter oiter;
76         BMFace *f, *f2 /* , *nf = NULL */;
77         BLI_array_declare(faces);
78         BLI_array_declare(regions);
79         BMFace ***regions = NULL;
80         BMFace **faces = NULL;
81         BMWalker regwalker;
82         int i;
83
84         int use_verts = BMO_slot_bool_get(op, "use_verts");
85
86         if (use_verts) {
87                 /* tag verts that start out with only 2 edges,
88                  * don't remove these later */
89                 BMIter viter;
90                 BMVert *v;
91
92                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
93                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
94                 }
95         }
96
97         BMO_slot_buffer_flag_enable(bm, op, "faces", BM_FACE, FACE_MARK);
98         
99         /* collect region */
100         BMO_ITER(f, &oiter, bm, op, "faces", BM_FACE) {
101
102                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) {
103                         continue;
104                 }
105
106                 BLI_array_empty(faces);
107                 faces = NULL; /* forces different allocatio */
108
109                 /* yay, walk */
110                 BMW_init(&regwalker, bm, BMW_ISLAND,
111                          BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK,
112                          BMW_FLAG_NOP, /* BMESH_TODO - should be BMW_FLAG_TEST_HIDDEN ? */
113                          BMW_NIL_LAY);
114
115                 f2 = BMW_begin(&regwalker, f);
116                 for ( ; f2; f2 = BMW_step(&regwalker)) {
117                         BLI_array_append(faces, f2);
118                 }
119                 BMW_end(&regwalker);
120                 
121                 for (i = 0; i < BLI_array_count(faces); i++) {
122                         f2 = faces[i];
123                         BMO_elem_flag_disable(bm, f2, FACE_MARK);
124                         BMO_elem_flag_enable(bm, f2, FACE_ORIG);
125                 }
126
127                 if (BMO_error_occurred(bm)) {
128                         BMO_error_clear(bm);
129                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
130                         goto cleanup;
131                 }
132                 
133                 BLI_array_append(faces, NULL);
134                 BLI_array_append(regions, faces);
135         }
136         
137         for (i = 0; i < BLI_array_count(regions); i++) {
138                 int tot = 0;
139                 
140                 faces = regions[i];
141                 if (!faces[0]) {
142                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
143                                         "Could not find boundary of dissolve region");
144                         goto cleanup;
145                 }
146                 
147                 while (faces[tot])
148                         tot++;
149                 
150                 f = BM_faces_join(bm, faces, tot, TRUE);
151                 if (!f) {
152                         BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED,
153                                         "Could not create merged face");
154                         goto cleanup;
155                 }
156
157                 /* if making the new face failed (e.g. overlapping test)
158                  * unmark the original faces for deletion */
159                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
160                 BMO_elem_flag_enable(bm, f, FACE_NEW);
161
162         }
163
164         BMO_op_callf(bm, "del geom=%ff context=%i", FACE_ORIG, DEL_FACES);
165
166
167         if (use_verts) {
168                 BMIter viter;
169                 BMVert *v;
170
171                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
172                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
173                                 if (BM_vert_edge_count(v) == 2) {
174                                         BM_vert_collapse_edge(bm, v->e, v, TRUE);
175                                 }
176                         }
177                 }
178         }
179
180         if (BMO_error_occurred(bm)) {
181                 goto cleanup;
182         }
183
184         BMO_slot_buffer_from_enabled_flag(bm, op, "regionout", BM_FACE, FACE_NEW);
185
186 cleanup:
187         /* free/cleanup */
188         for (i = 0; i < BLI_array_count(regions); i++) {
189                 if (regions[i]) MEM_freeN(regions[i]);
190         }
191
192         BLI_array_free(regions);
193 }
194
195 /* almost identical to dissolve edge, except it cleans up vertice */
196 void bmo_dissolve_edgeloop_exec(BMesh *bm, BMOperator *op)
197 {
198         /* BMOperator fop; */
199         BMOIter oiter;
200         BMIter iter;
201         BMVert *v, **verts = NULL;
202         BLI_array_declare(verts);
203         BMEdge *e;
204         BMFace *fa, *fb;
205         int i;
206
207
208         BMO_ITER(e, &oiter, bm, op, "edges", BM_EDGE) {
209                 if (BM_edge_face_pair(e, &fa, &fb)) {
210                         BMO_elem_flag_enable(bm, e->v1, VERT_MARK);
211                         BMO_elem_flag_enable(bm, e->v2, VERT_MARK);
212
213                         /* BMESH_TODO - check on delaying edge removal since we may end up removing more then
214                          * one edge, and later referene a removed edge */
215                         BM_faces_join_pair(bm, fa, fb, e, TRUE);
216                 }
217         }
218
219         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
220                 if (BMO_elem_flag_test(bm, v, VERT_MARK) && BM_vert_edge_count(v) == 2) {
221                         BLI_array_append(verts, v);
222                 }
223         }
224
225         /* clean up extreneous 2-valence vertice */
226         for (i = 0; i < BLI_array_count(verts); i++) {
227                 if (verts[i]->e) {
228                         BM_vert_collapse_edge(bm, verts[i]->e, verts[i], TRUE);
229                 }
230         }
231         
232         BLI_array_free(verts);
233
234         //BMO_op_initf(bm, &fop, "dissolve_faces faces=%ff", FACE_MARK);
235         //BMO_op_exec(bm, &fop);
236
237         //BMO_slot_copy(op, &fop, "regionout", "regionout");
238
239         //BMO_op_finish(bm, &fop);
240 }
241
242
243 void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op)
244 {
245         /* might want to make this an option or mode - campbell */
246
247         /* BMOperator fop; */
248         BMOIter eiter;
249         BMEdge *e;
250
251         BMIter viter;
252         BMVert *v;
253
254         int use_verts = BMO_slot_bool_get(op, "use_verts");
255
256         if (use_verts) {
257                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
258                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
259                 }
260         }
261
262         BMO_ITER(e, &eiter, bm, op, "edges", BM_EDGE) {
263                 BMFace *fa, *fb;
264
265                 if (BM_edge_face_pair(e, &fa, &fb)) {
266
267                         /* join faces */
268
269                         /* BMESH_TODO - check on delaying edge removal since we may end up removing more then
270                          * one edge, and later referene a removed edge */
271                         BM_faces_join_pair(bm, fa, fb, e, TRUE);
272                 }
273         }
274
275         if (use_verts) {
276                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
277                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
278                                 if (BM_vert_edge_count(v) == 2) {
279                                         BM_vert_collapse_edge(bm, v->e, v, TRUE);
280                                 }
281                         }
282                 }
283         }
284 }
285
286 static int test_extra_verts(BMesh *bm, BMVert *v)
287 {
288         BMIter iter, liter, iter2, iter3;
289         BMFace *f, *f2;
290         BMLoop *l;
291         BMEdge *e;
292         int found;
293
294         /* test faces around verts for verts that would be wronly killed
295          * by dissolve faces. */
296         f = BM_iter_new(&iter, bm, BM_FACES_OF_VERT, v);
297         for ( ; f; f = BM_iter_step(&iter)) {
298                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
299                 for ( ; l; l = BM_iter_step(&liter)) {
300                         if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) {
301                                 /* if an edge around a vert is a boundary edge,
302                                  * then dissolve faces won't destroy it.
303                                  * also if it forms a boundary with one
304                                  * of the face region */
305                                 found = FALSE;
306                                 e = BM_iter_new(&iter2, bm, BM_EDGES_OF_VERT, l->v);
307                                 for ( ; e; e = BM_iter_step(&iter2)) {
308                                         if (BM_edge_face_count(e) == 1) {
309                                                 found = TRUE;
310                                         }
311                                         f2 = BM_iter_new(&iter3, bm, BM_FACES_OF_EDGE, e);
312                                         for ( ; f2; f2 = BM_iter_step(&iter3)) {
313                                                 if (!BMO_elem_flag_test(bm, f2, FACE_MARK)) {
314                                                         found = TRUE;
315                                                         break;
316                                                 }
317                                         }
318                                         if (found == TRUE) {
319                                                 break;
320                                         }
321                                 }
322                                 if (found == FALSE) {
323                                         return FALSE;
324                                 }
325                         }
326                 }
327         }
328
329         return TRUE;
330 }
331 void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
332 {
333         BMIter iter, fiter;
334         BMVert *v;
335         BMFace *f;
336         /* int i; */
337
338         BMO_slot_buffer_flag_enable(bm, op, "verts", BM_VERT, VERT_MARK);
339         
340         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
341                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
342                         /* check if it's a two-valence ver */
343                         if (BM_vert_edge_count(v) == 2) {
344
345                                 /* collapse the ver */
346                                 /* previously the faces were joined, but collapsing between 2 edges
347                                  * gives some advantage/difference in using vertex-dissolve over edge-dissolve */
348 #if 0
349                                 BM_vert_collapse_faces(bm, v->e, v, 1.0f, TRUE, TRUE);
350 #else
351                                 BM_vert_collapse_edge(bm, v->e, v, TRUE);
352 #endif
353
354                                 continue;
355                         }
356
357                         f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
358                         for ( ; f; f = BM_iter_step(&fiter)) {
359                                 BMO_elem_flag_enable(bm, f, FACE_ORIG);
360                                 BMO_elem_flag_enable(bm, f, FACE_MARK);
361                         }
362                         
363                         /* check if our additions to the input to face dissolve
364                          * will destroy nonmarked vertices. */
365                         if (!test_extra_verts(bm, v)) {
366                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
367                                 for ( ; f; f = BM_iter_step(&fiter)) {
368                                         if (BMO_elem_flag_test(bm, f, FACE_ORIG)) {
369                                                 BMO_elem_flag_disable(bm, f, FACE_MARK);
370                                                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
371                                         }
372                                 }
373                         }
374                         else {
375                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
376                                 for ( ; f; f = BM_iter_step(&fiter)) {
377                                         BMO_elem_flag_disable(bm, f, FACE_ORIG);
378                                 }
379                         }
380                 }
381         }
382
383         BMO_op_callf(bm, "dissolve_faces faces=%ff", FACE_MARK);
384         if (BMO_error_occurred(bm)) {
385                 const char *msg;
386
387                 BMO_error_get(bm, &msg, NULL);
388                 BMO_error_clear(bm);
389                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg);
390         }
391         
392         /* clean up any remainin */
393         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
394                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
395                         if (!BM_vert_dissolve(bm, v)) {
396                                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
397                                 return;
398                         }
399                 }
400         }
401
402 }
403
404 /* this code is for cleaning up two-edged faces, it shall become
405  * it's own function one day */
406 #if 0
407 void dummy_exec(BMesh *bm, BMOperator *op)
408 {
409         {
410                 /* clean up two-edged face */
411                 /* basic idea is to keep joining 2-edged faces until their
412                  * gone.  this however relies on joining two 2-edged faces
413                  * together to work, which doesn't */
414                 found3 = 1;
415                 while (found3) {
416                         found3 = 0;
417                         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
418                                 if (!BM_face_validate(bm, f, stderr)) {
419                                         printf("error.\n");
420                                 }
421
422                                 if (f->len == 2) {
423                                         //this design relies on join faces working
424                                         //with two-edged faces properly.
425                                         //commenting this line disables the
426                                         //outermost loop.
427                                         //found3 = 1;
428                                         found2 = 0;
429                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
430                                         fe = l->e;
431                                         for ( ; l; l = BM_iter_step(&liter)) {
432                                                 f2 = BM_iter_new(&fiter, bm,
433                                                                 BM_FACES_OF_EDGE, l->e);
434                                                 for ( ; f2; f2 = BM_iter_step(&fiter)) {
435                                                         if (f2 != f) {
436                                                                 BM_faces_join_pair(bm, f, f2, l->e);
437                                                                 found2 = 1;
438                                                                 break;
439                                                         }
440                                                 }
441                                                 if (found2) break;
442                                         }
443
444                                         if (!found2) {
445                                                 BM_face_kill(bm, f);
446                                                 BM_edge_kill(bm, fe);
447                                         }
448                                 }
449                                 /* else if (f->len == 3) {
450                                         BMEdge *ed[3];
451                                         BMVert *vt[3];
452                                         BMLoop *lp[3];
453                                         int i = 0;
454
455                                         //check for duplicate edges
456                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
457                                         for ( ; l; l = BM_iter_step(&liter)) {
458                                                 ed[i] = l->e;
459                                                 lp[i] = l;
460                                                 vt[i++] = l->v;
461                                         }
462                                         if (vt[0] == vt[1] || vt[0] == vt[2]) {
463                                                 i += 1;
464                                         }
465                                  */
466                         }
467                 }
468                 if (oldlen == len) break;
469                 oldlen = len;
470         }
471 }
472
473 #endif
474
475 /* Limited Dissolve */
476
477 #define UNIT_TO_ANGLE DEG2RADF(90.0)
478 #define ANGLE_TO_UNIT (1.0 / UNIT_TO_ANGLE)
479
480 /* multiply vertex edge angle by face angle
481  * this means we are not left with sharp corners between _almost_ planer faces
482  * convert angles [0-PI/2] -> [0-1], multiply together, then convert back to radians. */
483 float bm_vert_edge_face_angle(BMVert *v)
484 {
485         const float angle = BM_vert_edge_angle(v);
486         /*note: could be either edge, it doesnt matter */
487         if (v->e && BM_edge_is_manifold(v->e)) {
488                 return ((angle * ANGLE_TO_UNIT) * (BM_edge_face_angle(v->e) * ANGLE_TO_UNIT)) * UNIT_TO_ANGLE;
489         }
490         else {
491                 return angle;
492         }
493 }
494
495 #undef UNIT_TO_ANGLE
496 #undef ANGLE_TO_UNIT
497
498 typedef struct DissolveElemWeight {
499         BMHeader *ele;
500         float weight;
501 } DissolveElemWeight;
502
503 static int dissolve_elem_cmp(const void *a1, const void *a2)
504 {
505         const struct DissolveElemWeight *d1 = a1, *d2 = a2;
506
507         if      (d1->weight > d2->weight) return  1;
508         else if (d1->weight < d2->weight) return -1;
509         return 0;
510 }
511
512 void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
513 {
514         BMOpSlot *einput = BMO_slot_get(op, "edges");
515         BMOpSlot *vinput = BMO_slot_get(op, "verts");
516         const float angle_max = (float)M_PI / 2.0f;
517         const float angle_limit = minf(angle_max, BMO_slot_float_get(op, "angle_limit"));
518         DissolveElemWeight *weight_elems = MEM_mallocN(MAX2(einput->len, vinput->len) *
519                                                          sizeof(DissolveElemWeight), __func__);
520         int i, tot_found;
521
522         /* --- first edges --- */
523
524         /* go through and split edge */
525         for (i = 0, tot_found = 0; i < einput->len; i++) {
526                 BMEdge *e = ((BMEdge **)einput->data.p)[i];
527                 const float angle = BM_edge_face_angle(e);
528
529                 if (angle < angle_limit) {
530                         tot_found++;
531                 }
532                 weight_elems[i].ele = (BMHeader *)e;
533                 weight_elems[i].weight = angle;
534         }
535
536         if (tot_found != 0) {
537                 qsort(weight_elems, einput->len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
538
539                 for (i = 0; i < tot_found; i++) {
540                         BMEdge *e = (BMEdge *)weight_elems[i].ele;
541
542                         if (/* may have become non-manifold */
543                             BM_edge_is_manifold(e) &&
544                             /* check twice because cumulative effect could dissolve over angle limit */
545                             (BM_edge_face_angle(e) < angle_limit))
546                         {
547                                 BMFace *nf = BM_faces_join_pair(bm, e->l->f,
548                                                                 e->l->radial_next->f,
549                                                                 e,
550                                                                 FALSE); /* join faces */
551
552                                 /* there may be some errors, we don't mind, just move on */
553                                 if (nf) {
554                                         BM_face_normal_update(bm, nf);
555                                 }
556                                 else {
557                                         BMO_error_clear(bm);
558                                 }
559                         }
560                 }
561
562                 /* remove all edges/verts left behind from dissolving */
563                 for (i = 0; i < einput->len; i++) {
564                         BMEdge *e = (BMEdge *)weight_elems[i].ele;
565                         if (BM_edge_is_wire(e)) {
566                                 BMVert *v1 = e->v1;
567                                 BMVert *v2 = e->v2;
568                                 BM_edge_kill(bm, e);
569                                 if (v1->e == NULL) BM_vert_kill(bm, v1);
570                                 if (v2->e == NULL) BM_vert_kill(bm, v2);
571                         }
572                 }
573         }
574
575         /* --- second verts --- */
576         for (i = 0, tot_found = 0; i < vinput->len; i++) {
577                 BMVert *v = ((BMVert **)vinput->data.p)[i];
578                 const float angle = bm_vert_edge_face_angle(v);
579
580                 if (angle < angle_limit) {
581                         weight_elems[i].ele = (BMHeader *)v;
582                         weight_elems[i].weight = angle;
583                         tot_found++;
584                 }
585                 else {
586                         weight_elems[i].ele = NULL;
587                         weight_elems[i].weight = angle_max;
588                 }
589         }
590
591         if (tot_found != 0) {
592                 qsort(weight_elems, vinput->len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
593
594                 for (i = 0; i < tot_found; i++) {
595                         BMVert *v = (BMVert *)weight_elems[i].ele;
596                         if (/* topology changes may cause this to be un-collapsable */
597                             (BM_vert_edge_count(v) == 2) &&
598                             /* check twice because cumulative effect could dissolve over angle limit */
599                             bm_vert_edge_face_angle(v) < angle_limit)
600                         {
601                                 BMEdge *ne = BM_vert_collapse_edge(bm, v->e, v, TRUE); /* join edges */
602
603                                 if (ne && ne->l) {
604                                         BM_edge_normals_update(bm, ne);
605                                 }
606                         }
607                 }
608         }
609
610         MEM_freeN(weight_elems);
611 }