diff options
Diffstat (limited to 'source/blender/bmesh/operators/bmo_removedoubles.c')
-rw-r--r-- | source/blender/bmesh/operators/bmo_removedoubles.c | 590 |
1 files changed, 590 insertions, 0 deletions
diff --git a/source/blender/bmesh/operators/bmo_removedoubles.c b/source/blender/bmesh/operators/bmo_removedoubles.c new file mode 100644 index 00000000000..2eb1cf7db3e --- /dev/null +++ b/source/blender/bmesh/operators/bmo_removedoubles.c @@ -0,0 +1,590 @@ +/* + * ***** 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_math.h" +#include "BLI_array.h" + +#include "BKE_customdata.h" + +#include "bmesh.h" +#include "bmesh_private.h" + +#include "bmesh_operators_private.h" /* own include */ + +static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op) +{ + BMIter liter; + BMLoop *l; + BMVert *v2, *doub; + int split = FALSE; + + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) { + v2 = BMO_slot_map_ptr_get(bm, op, "targetmap", l->v); + /* ok: if v2 is NULL (e.g. not in the map) then it's + * a target vert, otherwise it's a doubl */ + if ((v2 && BM_vert_in_face(f, v2)) && + (v2 != l->prev->v) && + (v2 != l->next->v)) + { + doub = l->v; + split = TRUE; + break; + } + } + + if (split && doub != v2) { + BMLoop *nl; + BMFace *f2 = BM_face_split(bm, f, doub, v2, &nl, NULL); + + remdoubles_splitface(f, bm, op); + remdoubles_splitface(f2, bm, op); + } +} + +#define ELE_DEL 1 +#define EDGE_COL 2 +#define FACE_MARK 2 + +#if 0 +int remdoubles_face_overlaps(BMesh *bm, BMVert **varr, + int len, BMFace *exclude, + BMFace **overlapface) +{ + BMIter vertfaces; + BMFace *f; + int i, amount; + + if (overlapface) *overlapface = NULL; + + for (i = 0; i < len; i++) { + f = BM_iter_new(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]); + while (f) { + amount = BM_verts_in_face(bm, f, varr, len); + if (amount >= len) { + if (overlapface) *overlapface = f; + return TRUE; + } + f = BM_iter_step(&vertfaces); + } + } + return FALSE; +} +#endif + +void bmesh_weldverts_exec(BMesh *bm, BMOperator *op) +{ + BMIter iter, liter; + BMVert *v, *v2; + BMEdge *e, *e2, **edges = NULL; + BLI_array_declare(edges); + BMLoop *l, *l2, **loops = NULL; + BLI_array_declare(loops); + BMFace *f, *f2; + int a, b; + + BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) { + if ((v2 = BMO_slot_map_ptr_get(bm, op, "targetmap", v))) { + BMO_elem_flag_enable(bm, v, ELE_DEL); + + /* merge the vertex flags, else we get randomly selected/unselected verts */ + BM_elem_flag_merge(v, v2); + } + } + + BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) { + remdoubles_splitface(f, bm, op); + } + + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + if (BMO_elem_flag_test(bm, e->v1, ELE_DEL) || BMO_elem_flag_test(bm, e->v2, ELE_DEL)) { + v = BMO_slot_map_ptr_get(bm, op, "targetmap", e->v1); + v2 = BMO_slot_map_ptr_get(bm, op, "targetmap", e->v2); + + if (!v) v = e->v1; + if (!v2) v2 = e->v2; + + if (v == v2) + BMO_elem_flag_enable(bm, e, EDGE_COL); + else if (!BM_edge_exists(v, v2)) + BM_edge_create(bm, v, v2, e, TRUE); + + BMO_elem_flag_enable(bm, e, ELE_DEL); + } + } + + /* BMESH_TODO, stop abusing face index here */ + BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) { + BM_elem_index_set(f, 0); /* set_dirty! */ + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) { + if (BMO_elem_flag_test(bm, l->v, ELE_DEL)) { + BMO_elem_flag_enable(bm, f, FACE_MARK|ELE_DEL); + } + if (BMO_elem_flag_test(bm, l->e, EDGE_COL)) { + BM_elem_index_set(f, BM_elem_index_get(f) + 1); /* set_dirty! */ + } + } + } + bm->elem_index_dirty |= BM_FACE; + + BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) { + if (!BMO_elem_flag_test(bm, f, FACE_MARK)) + continue; + + if (f->len - BM_elem_index_get(f) < 3) { + BMO_elem_flag_enable(bm, f, ELE_DEL); + continue; + } + + BLI_array_empty(edges); + BLI_array_empty(loops); + a = 0; + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) { + v = l->v; + v2 = l->next->v; + if (BMO_elem_flag_test(bm, v, ELE_DEL)) { + v = BMO_slot_map_ptr_get(bm, op, "targetmap", v); + } + if (BMO_elem_flag_test(bm, v2, ELE_DEL)) { + v2 = BMO_slot_map_ptr_get(bm, op, "targetmap", v2); + } + + e2 = v != v2 ? BM_edge_exists(v, v2) : NULL; + if (e2) { + for (b = 0; b < a; b++) { + if (edges[b] == e2) { + break; + } + } + if (b != a) { + continue; + } + + BLI_array_growone(edges); + BLI_array_growone(loops); + + edges[a] = e2; + loops[a] = l; + + a++; + } + } + + if (BLI_array_count(loops) < 3) + continue; + v = loops[0]->v; + v2 = loops[1]->v; + + if (BMO_elem_flag_test(bm, v, ELE_DEL)) { + v = BMO_slot_map_ptr_get(bm, op, "targetmap", v); + } + if (BMO_elem_flag_test(bm, v2, ELE_DEL)) { + v2 = BMO_slot_map_ptr_get(bm, op, "targetmap", v2); + } + + f2 = BM_face_create_ngon(bm, v, v2, edges, a, TRUE); + if (f2 && (f2 != f)) { + BM_elem_attrs_copy(bm, bm, f, f2); + + a = 0; + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f2) { + l2 = loops[a]; + BM_elem_attrs_copy(bm, bm, l2, l); + + a++; + } + } + } + + BMO_op_callf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED); + + BLI_array_free(edges); + BLI_array_free(loops); +} + +static int vergaverco(const void *e1, const void *e2) +{ + const BMVert *v1 = *(void **)e1, *v2 = *(void **)e2; + float x1 = v1->co[0] + v1->co[1] + v1->co[2]; + float x2 = v2->co[0] + v2->co[1] + v2->co[2]; + + if (x1 > x2) return 1; + else if (x1 < x2) return -1; + else return 0; +} + +#define VERT_TESTED 1 +#define VERT_DOUBLE 2 +#define VERT_TARGET 4 +#define VERT_KEEP 8 +#define VERT_MARK 16 +#define VERT_IN 32 + +#define EDGE_MARK 1 + +void bmesh_pointmerge_facedata_exec(BMesh *bm, BMOperator *op) +{ + BMOIter siter; + BMIter iter; + BMVert *v, *snapv; + BMLoop *l, *firstl = NULL; + float fac; + int i, tot; + + snapv = BMO_iter_new(&siter, bm, op, "snapv", BM_VERT); + tot = BM_vert_face_count(snapv); + + if (!tot) + return; + + fac = 1.0f / tot; + BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, snapv) { + if (!firstl) { + firstl = l; + } + + for (i = 0; i < bm->ldata.totlayer; i++) { + if (CustomData_layer_has_math(&bm->ldata, i)) { + int type = bm->ldata.layers[i].type; + void *e1, *e2; + + e1 = CustomData_bmesh_get_layer_n(&bm->ldata, firstl->head.data, i); + e2 = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i); + + CustomData_data_multiply(type, e2, fac); + + if (l != firstl) + CustomData_data_add(type, e1, e2); + } + } + } + + BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) { + BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) { + if (l == firstl) { + continue; + } + + CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, firstl->head.data, &l->head.data); + } + } +} + +void bmesh_vert_average_facedata_exec(BMesh *bm, BMOperator *op) +{ + BMOIter siter; + BMIter iter; + BMVert *v; + BMLoop *l /* , *firstl = NULL */; + CDBlockBytes min, max; + void *block; + int i, type; + + for (i = 0; i < bm->ldata.totlayer; i++) { + if (!CustomData_layer_has_math(&bm->ldata, i)) + continue; + + type = bm->ldata.layers[i].type; + CustomData_data_initminmax(type, &min, &max); + + BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) { + BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) { + block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i); + CustomData_data_dominmax(type, block, &min, &max); + } + } + + CustomData_data_multiply(type, &min, 0.5f); + CustomData_data_multiply(type, &max, 0.5f); + CustomData_data_add(type, &min, &max); + + BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) { + BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) { + block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i); + CustomData_data_copy_value(type, &min, block); + } + } + } +} + +void bmesh_pointmerge_exec(BMesh *bm, BMOperator *op) +{ + BMOperator weldop; + BMOIter siter; + BMVert *v, *snapv = NULL; + float vec[3]; + + BMO_slot_vec_get(op, "mergeco", vec); + + //BMO_op_callf(bm, "collapse_uvs edges=%s", op, "edges"); + BMO_op_init(bm, &weldop, "weldverts"); + + BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) { + if (!snapv) { + snapv = v; + copy_v3_v3(snapv->co, vec); + } + else { + BMO_slot_map_ptr_insert(bm, &weldop, "targetmap", v, snapv); + } + } + + BMO_op_exec(bm, &weldop); + BMO_op_finish(bm, &weldop); +} + +void bmesh_collapse_exec(BMesh *bm, BMOperator *op) +{ + BMOperator weldop; + BMWalker walker; + BMIter iter; + BMEdge *e, **edges = NULL; + BLI_array_declare(edges); + float min[3], max[3]; + int i, tot; + + BMO_op_callf(bm, "collapse_uvs edges=%s", op, "edges"); + BMO_op_init(bm, &weldop, "weldverts"); + + BMO_slot_buffer_flag_enable(bm, op, "edges", EDGE_MARK, BM_EDGE); + + BMW_init(&walker, bm, BMW_SHELL, + BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP, BMW_MASK_NOP, + BMW_NIL_LAY); + + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) + continue; + + e = BMW_begin(&walker, e->v1); + BLI_array_empty(edges); + + INIT_MINMAX(min, max); + for (tot = 0; e; tot++, e = BMW_step(&walker)) { + BLI_array_growone(edges); + edges[tot] = e; + + DO_MINMAX(e->v1->co, min, max); + DO_MINMAX(e->v2->co, min, max); + } + + add_v3_v3v3(min, min, max); + mul_v3_fl(min, 0.5f); + + /* snap edges to a point. for initial testing purposes anyway */ + for (i = 0; i < tot; i++) { + copy_v3_v3(edges[i]->v1->co, min); + copy_v3_v3(edges[i]->v2->co, min); + + if (edges[i]->v1 != edges[0]->v1) + BMO_slot_map_ptr_insert(bm, &weldop, "targetmap", edges[i]->v1, edges[0]->v1); + if (edges[i]->v2 != edges[0]->v1) + BMO_slot_map_ptr_insert(bm, &weldop, "targetmap", edges[i]->v2, edges[0]->v1); + } + } + + BMO_op_exec(bm, &weldop); + BMO_op_finish(bm, &weldop); + + BMW_end(&walker); + BLI_array_free(edges); +} + +/* uv collapse functio */ +static void bmesh_collapsecon_do_layer(BMesh *bm, BMOperator *op, int layer) +{ + BMIter iter, liter; + BMFace *f; + BMLoop *l, *l2; + BMWalker walker; + void **blocks = NULL; + BLI_array_declare(blocks); + CDBlockBytes min, max; + int i, tot, type = bm->ldata.layers[layer].type; + + /* clear all short flags */ + BMO_mesh_flag_disable_all(bm, op, BM_ALL, (1 << 16) - 1); + + BMO_slot_buffer_flag_enable(bm, op, "edges", EDGE_MARK, BM_EDGE); + + BMW_init(&walker, bm, BMW_LOOPDATA_ISLAND, + BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP, BMW_MASK_NOP, + layer); + + BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) { + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) { + if (BMO_elem_flag_test(bm, l->e, EDGE_MARK)) { + /* wal */ + BLI_array_empty(blocks); + tot = 0; + l2 = BMW_begin(&walker, l); + + CustomData_data_initminmax(type, &min, &max); + for (tot = 0; l2; tot++, l2 = BMW_step(&walker)) { + BLI_array_growone(blocks); + blocks[tot] = CustomData_bmesh_get_layer_n(&bm->ldata, l2->head.data, layer); + CustomData_data_dominmax(type, blocks[tot], &min, &max); + } + + if (tot) { + CustomData_data_multiply(type, &min, 0.5f); + CustomData_data_multiply(type, &max, 0.5f); + CustomData_data_add(type, &min, &max); + + /* snap CD (uv, vcol) points to their centroi */ + for (i = 0; i < tot; i++) { + CustomData_data_copy_value(type, &min, blocks[i]); + } + } + } + } + } + + BMW_end(&walker); + BLI_array_free(blocks); +} + +void bmesh_collapsecon_exec(BMesh *bm, BMOperator *op) +{ + int i; + + for (i = 0; i < bm->ldata.totlayer; i++) { + if (CustomData_layer_has_math(&bm->ldata, i)) + bmesh_collapsecon_do_layer(bm, op, i); + } +} + +void bmesh_finddoubles_common(BMesh *bm, BMOperator *op, BMOperator *optarget, const char *targetmapname) +{ + BMOIter oiter; + BMVert *v, *v2; + BMVert **verts = NULL; + BLI_array_declare(verts); + float dist, dist3; + int i, j, len, keepvert = 0; + + dist = BMO_slot_float_get(op, "dist"); + dist3 = dist * 3.0f; + + i = 0; + BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) { + BLI_array_growone(verts); + verts[i++] = v; + } + + /* Test whether keepverts arg exists and is non-empty */ + if (BMO_slot_exists(op, "keepverts")) { + keepvert = BMO_iter_new(&oiter, bm, op, "keepverts", BM_VERT) != NULL; + } + + /* sort by vertex coordinates added togethe */ + qsort(verts, BLI_array_count(verts), sizeof(void *), vergaverco); + + /* Flag keepverts */ + if (keepvert) { + BMO_slot_buffer_flag_enable(bm, op, "keepverts", VERT_KEEP, BM_VERT); + } + + len = BLI_array_count(verts); + for (i = 0; i < len; i++) { + v = verts[i]; + if (BMO_elem_flag_test(bm, v, VERT_DOUBLE)) continue; + + for (j = i + 1; j < len; j++) { + v2 = verts[j]; + + /* Compare sort values of the verts using 3x tolerance (allowing for the tolerance + * on each of the three axes). This avoids the more expensive length comparison + * for most vertex pairs. */ + if ((v2->co[0]+v2->co[1]+v2->co[2])-(v->co[0]+v->co[1]+v->co[2]) > dist3) + break; + + if (keepvert) { + if (BMO_elem_flag_test(bm, v2, VERT_KEEP) == BMO_elem_flag_test(bm, v, VERT_KEEP)) + continue; + } + + if (compare_len_v3v3(v->co, v2->co, dist)) { + + /* If one vert is marked as keep, make sure it will be the target */ + if (BMO_elem_flag_test(bm, v2, VERT_KEEP)) { + SWAP(BMVert *, v, v2); + } + + BMO_elem_flag_enable(bm, v2, VERT_DOUBLE); + BMO_elem_flag_enable(bm, v, VERT_TARGET); + + BMO_slot_map_ptr_insert(bm, optarget, targetmapname, v2, v); + } + } + } + + BLI_array_free(verts); +} + +void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op) +{ + BMOperator weldop; + + BMO_op_init(bm, &weldop, "weldverts"); + bmesh_finddoubles_common(bm, op, &weldop, "targetmap"); + BMO_op_exec(bm, &weldop); + BMO_op_finish(bm, &weldop); +} + + +void bmesh_finddoubles_exec(BMesh *bm, BMOperator *op) +{ + bmesh_finddoubles_common(bm, op, op, "targetmapout"); +} + +void bmesh_automerge_exec(BMesh *bm, BMOperator *op) +{ + BMOperator findop, weldop; + BMIter viter; + BMVert *v; + + /* The "verts" input sent to this op is the set of verts that + * can be merged away into any other verts. Mark all other verts + * as VERT_KEEP. */ + BMO_slot_buffer_flag_enable(bm, op, "verts", VERT_IN, BM_VERT); + BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) { + if (!BMO_elem_flag_test(bm, v, VERT_IN)) { + BMO_elem_flag_enable(bm, v, VERT_KEEP); + } + } + + /* Search for doubles among all vertices, but only merge non-VERT_KEEP + * vertices into VERT_KEEP vertices. */ + BMO_op_initf(bm, &findop, "finddoubles verts=%av keepverts=%fv", VERT_KEEP); + BMO_slot_copy(op, &findop, "dist", "dist"); + BMO_op_exec(bm, &findop); + + /* weld the vertices */ + BMO_op_init(bm, &weldop, "weldverts"); + BMO_slot_copy(&findop, &weldop, "targetmapout", "targetmap"); + BMO_op_exec(bm, &weldop); + + BMO_op_finish(bm, &findop); + BMO_op_finish(bm, &weldop); +} |