Merged changes in the trunk up to revision 45383.
[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);
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                         BM_faces_join_pair(bm, fa, fb, e);
214                 }
215         }
216
217         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
218                 if (BMO_elem_flag_test(bm, v, VERT_MARK) && BM_vert_edge_count(v) == 2) {
219                         BLI_array_append(verts, v);
220                 }
221         }
222
223         /* clean up extreneous 2-valence vertice */
224         for (i = 0; i < BLI_array_count(verts); i++) {
225                 if (verts[i]->e) {
226                         BM_vert_collapse_edge(bm, verts[i]->e, verts[i], TRUE);
227                 }
228         }
229         
230         BLI_array_free(verts);
231
232         //BMO_op_initf(bm, &fop, "dissolve_faces faces=%ff", FACE_MARK);
233         //BMO_op_exec(bm, &fop);
234
235         //BMO_slot_copy(op, &fop, "regionout", "regionout");
236
237         //BMO_op_finish(bm, &fop);
238 }
239
240
241 void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op)
242 {
243         /* might want to make this an option or mode - campbell */
244
245         /* BMOperator fop; */
246         BMOIter eiter;
247         BMEdge *e;
248
249         BMIter viter;
250         BMVert *v;
251
252         int use_verts = BMO_slot_bool_get(op, "use_verts");
253
254         if (use_verts) {
255                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
256                         BMO_elem_flag_set(bm, v, VERT_MARK, (BM_vert_edge_count(v) != 2));
257                 }
258         }
259
260         BMO_ITER(e, &eiter, bm, op, "edges", BM_EDGE) {
261                 BMFace *fa, *fb;
262
263                 if (BM_edge_face_pair(e, &fa, &fb)) {
264
265                         /* join faces */
266                         BM_faces_join_pair(bm, fa, fb, e);
267                 }
268         }
269
270         if (use_verts) {
271                 BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
272                         if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
273                                 if (BM_vert_edge_count(v) == 2) {
274                                         BM_vert_collapse_edge(bm, v->e, v, TRUE);
275                                 }
276                         }
277                 }
278         }
279 }
280
281 static int test_extra_verts(BMesh *bm, BMVert *v)
282 {
283         BMIter iter, liter, iter2, iter3;
284         BMFace *f, *f2;
285         BMLoop *l;
286         BMEdge *e;
287         int found;
288
289         /* test faces around verts for verts that would be wronly killed
290          * by dissolve faces. */
291         f = BM_iter_new(&iter, bm, BM_FACES_OF_VERT, v);
292         for ( ; f; f = BM_iter_step(&iter)) {
293                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
294                 for ( ; l; l = BM_iter_step(&liter)) {
295                         if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) {
296                                 /* if an edge around a vert is a boundary edge,
297                                  * then dissolve faces won't destroy it.
298                                  * also if it forms a boundary with one
299                                  * of the face region */
300                                 found = FALSE;
301                                 e = BM_iter_new(&iter2, bm, BM_EDGES_OF_VERT, l->v);
302                                 for ( ; e; e = BM_iter_step(&iter2)) {
303                                         if (BM_edge_face_count(e) == 1) {
304                                                 found = TRUE;
305                                         }
306                                         f2 = BM_iter_new(&iter3, bm, BM_FACES_OF_EDGE, e);
307                                         for ( ; f2; f2 = BM_iter_step(&iter3)) {
308                                                 if (!BMO_elem_flag_test(bm, f2, FACE_MARK)) {
309                                                         found = TRUE;
310                                                         break;
311                                                 }
312                                         }
313                                         if (found == TRUE) {
314                                                 break;
315                                         }
316                                 }
317                                 if (found == FALSE) {
318                                         return FALSE;
319                                 }
320                         }
321                 }
322         }
323
324         return TRUE;
325 }
326 void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
327 {
328         BMIter iter, fiter;
329         BMVert *v;
330         BMFace *f;
331         /* int i; */
332
333         BMO_slot_buffer_flag_enable(bm, op, "verts", BM_VERT, VERT_MARK);
334         
335         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
336                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
337                         /* check if it's a two-valence ver */
338                         if (BM_vert_edge_count(v) == 2) {
339
340                                 /* collapse the ver */
341                                 /* previously the faces were joined, but collapsing between 2 edges
342                                  * gives some advantage/difference in using vertex-dissolve over edge-dissolve */
343 #if 0
344                                 BM_vert_collapse_faces(bm, v->e, v, 1.0f, TRUE, TRUE);
345 #else
346                                 BM_vert_collapse_edge(bm, v->e, v, TRUE);
347 #endif
348
349                                 continue;
350                         }
351
352                         f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
353                         for ( ; f; f = BM_iter_step(&fiter)) {
354                                 BMO_elem_flag_enable(bm, f, FACE_ORIG);
355                                 BMO_elem_flag_enable(bm, f, FACE_MARK);
356                         }
357                         
358                         /* check if our additions to the input to face dissolve
359                          * will destroy nonmarked vertices. */
360                         if (!test_extra_verts(bm, v)) {
361                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
362                                 for ( ; f; f = BM_iter_step(&fiter)) {
363                                         if (BMO_elem_flag_test(bm, f, FACE_ORIG)) {
364                                                 BMO_elem_flag_disable(bm, f, FACE_MARK);
365                                                 BMO_elem_flag_disable(bm, f, FACE_ORIG);
366                                         }
367                                 }
368                         }
369                         else {
370                                 f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v);
371                                 for ( ; f; f = BM_iter_step(&fiter)) {
372                                         BMO_elem_flag_disable(bm, f, FACE_ORIG);
373                                 }
374                         }
375                 }
376         }
377
378         BMO_op_callf(bm, "dissolve_faces faces=%ff", FACE_MARK);
379         if (BMO_error_occurred(bm)) {
380                 const char *msg;
381
382                 BMO_error_get(bm, &msg, NULL);
383                 BMO_error_clear(bm);
384                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg);
385         }
386         
387         /* clean up any remainin */
388         for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) {
389                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
390                         if (!BM_vert_dissolve(bm, v)) {
391                                 BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
392                                 return;
393                         }
394                 }
395         }
396
397 }
398
399 /* this code is for cleaning up two-edged faces, it shall become
400  * it's own function one day */
401 #if 0
402 void dummy_exec(BMesh *bm, BMOperator *op)
403 {
404         {
405                 /* clean up two-edged face */
406                 /* basic idea is to keep joining 2-edged faces until their
407                  * gone.  this however relies on joining two 2-edged faces
408                  * together to work, which doesn't */
409                 found3 = 1;
410                 while (found3) {
411                         found3 = 0;
412                         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
413                                 if (!BM_face_validate(bm, f, stderr)) {
414                                         printf("error.\n");
415                                 }
416
417                                 if (f->len == 2) {
418                                         //this design relies on join faces working
419                                         //with two-edged faces properly.
420                                         //commenting this line disables the
421                                         //outermost loop.
422                                         //found3 = 1;
423                                         found2 = 0;
424                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
425                                         fe = l->e;
426                                         for ( ; l; l = BM_iter_step(&liter)) {
427                                                 f2 = BM_iter_new(&fiter, bm,
428                                                                 BM_FACES_OF_EDGE, l->e);
429                                                 for ( ; f2; f2 = BM_iter_step(&fiter)) {
430                                                         if (f2 != f) {
431                                                                 BM_faces_join_pair(bm, f, f2, l->e);
432                                                                 found2 = 1;
433                                                                 break;
434                                                         }
435                                                 }
436                                                 if (found2) break;
437                                         }
438
439                                         if (!found2) {
440                                                 BM_face_kill(bm, f);
441                                                 BM_edge_kill(bm, fe);
442                                         }
443                                 }
444                                 /* else if (f->len == 3) {
445                                         BMEdge *ed[3];
446                                         BMVert *vt[3];
447                                         BMLoop *lp[3];
448                                         int i = 0;
449
450                                         //check for duplicate edges
451                                         l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
452                                         for ( ; l; l = BM_iter_step(&liter)) {
453                                                 ed[i] = l->e;
454                                                 lp[i] = l;
455                                                 vt[i++] = l->v;
456                                         }
457                                         if (vt[0] == vt[1] || vt[0] == vt[2]) {
458                                                 i += 1;
459                                         }
460                                  */
461                         }
462                 }
463                 if (oldlen == len) break;
464                 oldlen = len;
465         }
466 }
467
468 #endif
469
470 /**/
471 typedef struct DissolveElemWeight {
472         BMHeader *ele;
473         float weight;
474 } DissolveElemWeight;
475
476 static int dissolve_elem_cmp(const void *a1, const void *a2)
477 {
478         const struct DissolveElemWeight *d1 = a1, *d2 = a2;
479
480         if      (d1->weight > d2->weight) return  1;
481         else if (d1->weight < d2->weight) return -1;
482         return 0;
483 }
484
485 void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
486 {
487         BMOpSlot *einput = BMO_slot_get(op, "edges");
488         BMOpSlot *vinput = BMO_slot_get(op, "verts");
489         const float angle_max = (float)M_PI / 2.0f;
490         const float angle_limit = minf(angle_max, BMO_slot_float_get(op, "angle_limit"));
491         DissolveElemWeight *weight_elems = MEM_mallocN(MAX2(einput->len, vinput->len) *
492                                                          sizeof(DissolveElemWeight), __func__);
493         int i, tot_found;
494
495         /* --- first edges --- */
496
497         /* go through and split edge */
498         for (i = 0, tot_found = 0; i < einput->len; i++) {
499                 BMEdge *e = ((BMEdge **)einput->data.p)[i];
500                 const float angle = BM_edge_face_angle(e);
501
502                 if (angle < angle_limit) {
503                         weight_elems[i].ele = (BMHeader *)e;
504                         weight_elems[i].weight = angle;
505                         tot_found++;
506                 }
507                 else {
508                         weight_elems[i].ele = NULL;
509                         weight_elems[i].weight = angle_max;
510                 }
511         }
512
513         if (tot_found != 0) {
514                 qsort(weight_elems, einput->len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
515
516                 for (i = 0; i < tot_found; i++) {
517                         BMEdge *e = (BMEdge *)weight_elems[i].ele;
518                         /* check twice because cumulative effect could dissolve over angle limit */
519                         if (BM_edge_face_angle(e) < angle_limit) {
520                                 BMFace *nf = BM_faces_join_pair(bm, e->l->f,
521                                                                 e->l->radial_next->f,
522                                                                 e); /* join faces */
523
524                                 /* there may be some errors, we don't mind, just move on */
525                                 if (nf == NULL) {
526                                         BMO_error_clear(bm);
527                                 }
528                         }
529                 }
530         }
531
532         /* --- second verts --- */
533         for (i = 0, tot_found = 0; i < vinput->len; i++) {
534                 BMVert *v = ((BMVert **)vinput->data.p)[i];
535                 const float angle = BM_vert_edge_angle(v);
536
537                 if (angle < angle_limit) {
538                         weight_elems[i].ele = (BMHeader *)v;
539                         weight_elems[i].weight = angle;
540                         tot_found++;
541                 }
542                 else {
543                         weight_elems[i].ele = NULL;
544                         weight_elems[i].weight = angle_max;
545                 }
546         }
547
548         if (tot_found != 0) {
549                 qsort(weight_elems, vinput->len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
550
551                 for (i = 0; i < tot_found; i++) {
552                         BMVert *v = (BMVert *)weight_elems[i].ele;
553                         /* check twice because cumulative effect could dissolve over angle limit */
554                         if (BM_vert_edge_angle(v) < angle_limit) {
555                                 BM_vert_collapse_edge(bm, v->e, v, TRUE); /* join edges */
556                         }
557                 }
558         }
559
560         MEM_freeN(weight_elems);
561 }