diff options
Diffstat (limited to 'source/blender/bmesh/operators/bmo_dissolve.c')
-rw-r--r-- | source/blender/bmesh/operators/bmo_dissolve.c | 559 |
1 files changed, 559 insertions, 0 deletions
diff --git a/source/blender/bmesh/operators/bmo_dissolve.c b/source/blender/bmesh/operators/bmo_dissolve.c new file mode 100644 index 00000000000..05aead466d1 --- /dev/null +++ b/source/blender/bmesh/operators/bmo_dissolve.c @@ -0,0 +1,559 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Joseph Eagar. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_array.h" +#include "BLI_math.h" + +#include "bmesh.h" +#include "bmesh_private.h" + +#include "bmesh_operators_private.h" /* own include */ + +#define FACE_MARK 1 +#define FACE_ORIG 2 +#define FACE_NEW 4 +#define EDGE_MARK 1 + +#define VERT_MARK 1 + +static int UNUSED_FUNCTION(check_hole_in_region)(BMesh *bm, BMFace *f) +{ + BMWalker regwalker; + BMIter liter2; + BMLoop *l2, *l3; + BMFace *f2; + + /* checks if there are any unmarked boundary edges in the face regio */ + + BMW_init(®walker, bm, BMW_ISLAND, + BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK, + BMW_NIL_LAY); + f2 = BMW_begin(®walker, f); + for ( ; f2; f2 = BMW_step(®walker)) { + l2 = BM_iter_new(&liter2, bm, BM_LOOPS_OF_FACE, f2); + for ( ; l2; l2 = BM_iter_step(&liter2)) { + l3 = bmesh_radial_nextloop(l2); + if ( BMO_elem_flag_test(bm, l3->f, FACE_MARK) != + BMO_elem_flag_test(bm, l2->f, FACE_MARK)) + { + if (!BMO_elem_flag_test(bm, l2->e, EDGE_MARK)) { + return FALSE; + } + } + } + } + BMW_end(®walker); + + return TRUE; +} + +void dissolvefaces_exec(BMesh *bm, BMOperator *op) +{ + BMOIter oiter; + BMFace *f, *f2 /* , *nf = NULL */; + BLI_array_declare(faces); + BLI_array_declare(regions); + BMFace ***regions = NULL; + BMFace **faces = NULL; + BMWalker regwalker; + int i; + + int use_verts = BMO_slot_int_get(op, "use_verts"); + + if (use_verts) { + /* tag verts that start out with only 2 edges, + * don't remove these later */ + BMIter viter; + BMVert *v; + + BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) { + if (BM_vert_edge_count(v) == 2) { + BMO_elem_flag_disable(bm, v, VERT_MARK); + } + else { + BMO_elem_flag_enable(bm, v, VERT_MARK); + } + } + } + + BMO_slot_buffer_flag_enable(bm, op, "faces", FACE_MARK, BM_FACE); + + /* collect region */ + BMO_ITER(f, &oiter, bm, op, "faces", BM_FACE) { + if (!BMO_elem_flag_test(bm, f, FACE_MARK)) continue; + + BLI_array_empty(faces); + faces = NULL; /* forces different allocatio */ + + /* yay, walk */ + BMW_init(®walker, bm, BMW_ISLAND, + BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP, FACE_MARK, + BMW_NIL_LAY); + + f2 = BMW_begin(®walker, f); + for ( ; f2; f2 = BMW_step(®walker)) { + BLI_array_append(faces, f2); + } + BMW_end(®walker); + + for (i = 0; i < BLI_array_count(faces); i++) { + f2 = faces[i]; + BMO_elem_flag_disable(bm, f2, FACE_MARK); + BMO_elem_flag_enable(bm, f2, FACE_ORIG); + } + + if (BMO_error_occurred(bm)) { + BMO_error_clear(bm); + BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL); + goto cleanup; + } + + BLI_array_append(faces, NULL); + BLI_array_append(regions, faces); + } + + for (i = 0; i < BLI_array_count(regions); i++) { + int tot = 0; + + faces = regions[i]; + if (!faces[0]) { + BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, + "Could not find boundary of dissolve region"); + goto cleanup; + } + + while (faces[tot]) + tot++; + + f = BM_faces_join(bm, faces, tot); + if (!f) { + BMO_error_raise(bm, op, BMERR_DISSOLVEFACES_FAILED, + "Could not create merged face"); + goto cleanup; + } + + /* if making the new face failed (e.g. overlapping test) + * unmark the original faces for deletion */ + BMO_elem_flag_disable(bm, f, FACE_ORIG); + BMO_elem_flag_enable(bm, f, FACE_NEW); + + } + + BMO_op_callf(bm, "del geom=%ff context=%d", FACE_ORIG, DEL_FACES); + + + if (use_verts) { + BMIter viter; + BMVert *v; + + BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) { + if (BMO_elem_flag_test(bm, v, VERT_MARK)) { + if (BM_vert_edge_count(v) == 2) { + BM_vert_collapse_edges(bm, v->e, v); + } + } + } + } + + if (BMO_error_occurred(bm)) goto cleanup; + + BMO_slot_from_flag(bm, op, "regionout", FACE_NEW, BM_FACE); + +cleanup: + /* free/cleanu */ + for (i = 0; i < BLI_array_count(regions); i++) { + if (regions[i]) MEM_freeN(regions[i]); + } + + BLI_array_free(regions); +} + +/* almost identical to dissolve edge, except it cleans up vertice */ +void dissolve_edgeloop_exec(BMesh *bm, BMOperator *op) +{ + /* BMOperator fop; */ + BMOIter oiter; + BMIter iter; + BMVert *v, **verts = NULL; + BLI_array_declare(verts); + BMEdge *e; + /* BMFace *f; */ + int i; + + BMO_ITER(e, &oiter, bm, op, "edges", BM_EDGE) { + if (BM_edge_face_count(e) == 2) { + BMO_elem_flag_enable(bm, e->v1, VERT_MARK); + BMO_elem_flag_enable(bm, e->v2, VERT_MARK); + + BM_faces_join_pair(bm, e->l->f, + e->l->radial_next->f, + e); + } + } + + BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) { + if (BMO_elem_flag_test(bm, v, VERT_MARK) && BM_vert_edge_count(v) == 2) { + BLI_array_append(verts, v); + } + } + + /* clean up extreneous 2-valence vertice */ + for (i = 0; i < BLI_array_count(verts); i++) { + if (verts[i]->e) { + BM_vert_collapse_edges(bm, verts[i]->e, verts[i]); + } + } + + BLI_array_free(verts); + + //BMO_op_initf(bm, &fop, "dissolvefaces faces=%ff", FACE_MARK); + //BMO_op_exec(bm, &fop); + + //BMO_slot_copy(op, &fop, "regionout", "regionout"); + + //BMO_op_finish(bm, &fop); +} + + +void dissolveedges_exec(BMesh *bm, BMOperator *op) +{ + /* might want to make this an option or mode - campbell */ + + /* BMOperator fop; */ + BMOIter eiter; + BMEdge *e; + + BMIter viter; + BMVert *v; + + int use_verts = BMO_slot_int_get(op, "use_verts"); + + if (use_verts) { + BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) { + if (BM_vert_edge_count(v) == 2) { + BMO_elem_flag_disable(bm, v, VERT_MARK); + } + else { + BMO_elem_flag_enable(bm, v, VERT_MARK); + } + } + } + + BMO_ITER(e, &eiter, bm, op, "edges", BM_EDGE) { + const int edge_face_count = BM_edge_face_count(e); + if (edge_face_count == 2) { + + /* join faces */ + BM_faces_join_pair(bm, e->l->f, + e->l->radial_next->f, + e); + } + } + + if (use_verts) { + BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) { + if (BMO_elem_flag_test(bm, v, VERT_MARK)) { + if (BM_vert_edge_count(v) == 2) { + BM_vert_collapse_edges(bm, v->e, v); + } + } + } + } +} + +static int test_extra_verts(BMesh *bm, BMVert *v) +{ + BMIter iter, liter, iter2, iter3; + BMFace *f, *f2; + BMLoop *l; + BMEdge *e; + int found; + + /* test faces around verts for verts that would be wronly killed + * by dissolve faces. */ + f = BM_iter_new(&iter, bm, BM_FACES_OF_VERT, v); + for ( ; f; f = BM_iter_step(&iter)) { + l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f); + for ( ; l; l = BM_iter_step(&liter)) { + if (!BMO_elem_flag_test(bm, l->v, VERT_MARK)) { + /* if an edge around a vert is a boundary edge, + * then dissolve faces won't destroy it. + * also if it forms a boundary with one + * of the face region */ + found = FALSE; + e = BM_iter_new(&iter2, bm, BM_EDGES_OF_VERT, l->v); + for ( ; e; e = BM_iter_step(&iter2)) { + if (BM_edge_face_count(e) == 1) { + found = TRUE; + } + f2 = BM_iter_new(&iter3, bm, BM_FACES_OF_EDGE, e); + for ( ; f2; f2 = BM_iter_step(&iter3)) { + if (!BMO_elem_flag_test(bm, f2, FACE_MARK)) { + found = TRUE; + break; + } + } + if (found == TRUE) { + break; + } + } + if (found == FALSE) { + return FALSE; + } + } + } + } + + return TRUE; +} +void dissolveverts_exec(BMesh *bm, BMOperator *op) +{ + BMOpSlot *vinput; + BMIter iter, fiter; + BMVert *v; + BMFace *f; + /* int i; */ + + vinput = BMO_slot_get(op, "verts"); + BMO_slot_buffer_flag_enable(bm, op, "verts", VERT_MARK, BM_VERT); + + for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) { + if (BMO_elem_flag_test(bm, v, VERT_MARK)) { + /* check if it's a two-valence ver */ + if (BM_vert_edge_count(v) == 2) { + + /* collapse the ver */ + BM_vert_collapse_faces(bm, v->e, v, 1.0f, TRUE); + continue; + } + + f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v); + for ( ; f; f = BM_iter_step(&fiter)) { + BMO_elem_flag_enable(bm, f, FACE_ORIG); + BMO_elem_flag_enable(bm, f, FACE_MARK); + } + + /* check if our additions to the input to face dissolve + * will destroy nonmarked vertices. */ + if (!test_extra_verts(bm, v)) { + f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v); + for ( ; f; f = BM_iter_step(&fiter)) { + if (BMO_elem_flag_test(bm, f, FACE_ORIG)) { + BMO_elem_flag_disable(bm, f, FACE_MARK); + BMO_elem_flag_disable(bm, f, FACE_ORIG); + } + } + } + else { + f = BM_iter_new(&fiter, bm, BM_FACES_OF_VERT, v); + for ( ; f; f = BM_iter_step(&fiter)) { + BMO_elem_flag_disable(bm, f, FACE_ORIG); + } + } + } + } + + BMO_op_callf(bm, "dissolvefaces faces=%ff", FACE_MARK); + if (BMO_error_occurred(bm)) { + const char *msg; + + BMO_error_get(bm, &msg, NULL); + BMO_error_clear(bm); + BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, msg); + } + + /* clean up any remainin */ + for (v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v = BM_iter_step(&iter)) { + if (BMO_elem_flag_test(bm, v, VERT_MARK)) { + if (!BM_vert_dissolve(bm, v)) { + BMO_error_raise(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL); + return; + } + } + } + +} + +/* this code is for cleaning up two-edged faces, it shall become + * it's own function one day */ +#if 0 +void dummy_exec(BMesh *bm, BMOperator *op) +{ + { + /* clean up two-edged face */ + /* basic idea is to keep joining 2-edged faces until their + * gone. this however relies on joining two 2-edged faces + * together to work, which doesn't */ + found3 = 1; + while (found3) { + found3 = 0; + for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) { + if (!BM_face_validate(bm, f, stderr)) { + printf("error.\n"); + } + + if (f->len == 2) { + //this design relies on join faces working + //with two-edged faces properly. + //commenting this line disables the + //outermost loop. + //found3 = 1; + found2 = 0; + l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f); + fe = l->e; + for ( ; l; l = BM_iter_step(&liter)) { + f2 = BM_iter_new(&fiter, bm, + BM_FACES_OF_EDGE, l->e); + for ( ; f2; f2 = BM_iter_step(&fiter)) { + if (f2 != f) { + BM_faces_join_pair(bm, f, f2, l->e); + found2 = 1; + break; + } + } + if (found2) break; + } + + if (!found2) { + bmesh_kf(bm, f); + bmesh_ke(bm, fe); + } + } /* else if (f->len == 3) { + BMEdge *ed[3]; + BMVert *vt[3]; + BMLoop *lp[3]; + int i = 0; + + //check for duplicate edges + l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f); + for ( ; l; l = BM_iter_step(&liter)) { + ed[i] = l->e; + lp[i] = l; + vt[i++] = l->v; + } + if (vt[0] == vt[1] || vt[0] == vt[2]) { + i += 1; + } + */ + } + } + if (oldlen == len) break; + oldlen = len; + } +} + +#endif + +/**/ +typedef struct DissolveElemWeight_t { + BMHeader *ele; + float weight; +} DissolveElemWeight_t; + +static int dissolve_elem_cmp(const void *a1, const void *a2) +{ + const struct DissolveElemWeight_t *d1 = a1, *d2 = a2; + + if (d1->weight > d2->weight) return 1; + else if (d1->weight < d2->weight) return -1; + return 0; +} + +void dissolvelimit_exec(BMesh *bm, BMOperator *op) +{ + BMOpSlot *einput = BMO_slot_get(op, "edges"); + BMOpSlot *vinput = BMO_slot_get(op, "verts"); + const float angle_max = (float)M_PI / 2.0f; + const float angle_limit = minf(angle_max, BMO_slot_float_get(op, "angle_limit")); + DissolveElemWeight_t *weight_elems = MEM_mallocN(MAX2(einput->len, vinput->len) * + sizeof(DissolveElemWeight_t), __func__); + int i, tot_found; + + /* --- first edges --- */ + + /* go through and split edge */ + for (i = 0, tot_found = 0; i < einput->len; i++) { + BMEdge *e = ((BMEdge **)einput->data.p)[i]; + const float angle = BM_edge_face_angle(bm, e); + + if (angle < angle_limit) { + weight_elems[i].ele = (BMHeader *)e; + weight_elems[i].weight = angle; + tot_found++; + } + else { + weight_elems[i].ele = NULL; + weight_elems[i].weight = angle_max; + } + } + + if (tot_found != 0) { + qsort(weight_elems, einput->len, sizeof(DissolveElemWeight_t), dissolve_elem_cmp); + + for (i = 0; i < tot_found; i++) { + BMEdge *e = (BMEdge *)weight_elems[i].ele; + /* check twice because cumulative effect could disolve over angle limit */ + if (BM_edge_face_angle(bm, e) < angle_limit) { + BMFace *nf = BM_faces_join_pair(bm, e->l->f, + e->l->radial_next->f, + e); /* join faces */ + + /* there may be some errors, we dont mind, just move on */ + if (nf == NULL) { + BMO_error_clear(bm); + } + } + } + } + + /* --- second verts --- */ + for (i = 0, tot_found = 0; i < vinput->len; i++) { + BMVert *v = ((BMVert **)vinput->data.p)[i]; + const float angle = BM_vert_edge_angle(bm, v); + + if (angle < angle_limit) { + weight_elems[i].ele = (BMHeader *)v; + weight_elems[i].weight = angle; + tot_found++; + } + else { + weight_elems[i].ele = NULL; + weight_elems[i].weight = angle_max; + } + } + + if (tot_found != 0) { + qsort(weight_elems, vinput->len, sizeof(DissolveElemWeight_t), dissolve_elem_cmp); + + for (i = 0; i < tot_found; i++) { + BMVert *v = (BMVert *)weight_elems[i].ele; + /* check twice because cumulative effect could disolve over angle limit */ + if (BM_vert_edge_angle(bm, v) < angle_limit) { + BM_vert_collapse_edges(bm, v->e, v); /* join edges */ + } + } + } + + MEM_freeN(weight_elems); +} |