From afc56a0b10b52d2c8bdfd44257624d776db72f79 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 19 Feb 2012 18:31:04 +0000 Subject: copying bmesh dir on its own from bmesh branch --- source/blender/bmesh/operators/bmo_connect.c | 414 +++++++++++++++++++++++++++ 1 file changed, 414 insertions(+) create mode 100644 source/blender/bmesh/operators/bmo_connect.c (limited to 'source/blender/bmesh/operators/bmo_connect.c') diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c new file mode 100644 index 00000000000..6ab6d28008b --- /dev/null +++ b/source/blender/bmesh/operators/bmo_connect.c @@ -0,0 +1,414 @@ +/* + * ***** 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 "bmesh.h" + +#include "BLI_math.h" +#include "BLI_array.h" + +#define VERT_INPUT 1 +#define EDGE_OUT 1 +#define FACE_NEW 2 +#define EDGE_MARK 4 +#define EDGE_DONE 8 + +void connectverts_exec(BMesh *bm, BMOperator *op) +{ + BMIter iter, liter; + BMFace *f, *nf; + BMLoop **loops = NULL, *lastl = NULL; + BLI_array_declare(loops); + BMLoop *l, *nl; + BMVert **verts = NULL; + BLI_array_declare(verts); + int i; + + BMO_slot_buffer_flag_enable(bm, op, "verts", VERT_INPUT, BM_VERT); + + for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) { + BLI_array_empty(loops); + BLI_array_empty(verts); + + if (BMO_elem_flag_test(bm, f, FACE_NEW)) continue; + + l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f); + lastl = NULL; + for ( ; l; l = BM_iter_step(&liter)) { + if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) { + if (!lastl) { + lastl = l; + continue; + } + + if (lastl != l->prev && lastl != l->next) { + BLI_array_growone(loops); + loops[BLI_array_count(loops) - 1] = lastl; + + BLI_array_growone(loops); + loops[BLI_array_count(loops) - 1] = l; + + } + lastl = l; + } + } + + if (BLI_array_count(loops) == 0) continue; + + if (BLI_array_count(loops) > 2) { + BLI_array_growone(loops); + loops[BLI_array_count(loops) - 1] = loops[BLI_array_count(loops) - 2]; + + BLI_array_growone(loops); + loops[BLI_array_count(loops) - 1] = loops[0]; + } + + BM_face_legal_splits(bm, f, (BMLoop *(*)[2])loops, BLI_array_count(loops) / 2); + + for (i = 0; i < BLI_array_count(loops) / 2; i++) { + if (loops[i * 2] == NULL) continue; + + BLI_array_growone(verts); + verts[BLI_array_count(verts) - 1] = loops[i * 2]->v; + + BLI_array_growone(verts); + verts[BLI_array_count(verts) - 1] = loops[i * 2 + 1]->v; + } + + for (i = 0; i < BLI_array_count(verts) / 2; i++) { + nf = BM_face_split(bm, f, verts[i * 2], verts[i * 2 + 1], &nl, NULL); + f = nf; + + if (!nl || !nf) { + BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL); + BLI_array_free(loops); + return; + } + BMO_elem_flag_enable(bm, nf, FACE_NEW); + BMO_elem_flag_enable(bm, nl->e, EDGE_OUT); + } + } + + BMO_slot_from_flag(bm, op, "edgeout", EDGE_OUT, BM_EDGE); + + BLI_array_free(loops); + BLI_array_free(verts); +} + +static BMVert *get_outer_vert(BMesh *bm, BMEdge *e) +{ + BMIter iter; + BMEdge *e2; + int i; + + i = 0; + BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, e->v1) { + if (BMO_elem_flag_test(bm, e2, EDGE_MARK)) { + i++; + } + } + + return (i == 2) ? e->v2 : e->v1; +} + +/* Clamp x to the interval {0..len-1}, with wrap-around */ +static int clamp_index(const int x, const int len) +{ + return (x < 0) ? (len - (-x % len)) : (x % len); +} + +/* There probably is a better way to swap BLI_arrays, or if there + * isn't there should be... */ +#define ARRAY_SWAP(elemtype, arr1, arr2) \ + { \ + int i; \ + elemtype *arr_tmp = NULL; \ + BLI_array_declare(arr_tmp); \ + for (i = 0; i < BLI_array_count(arr1); i++) { \ + BLI_array_append(arr_tmp, arr1[i]); \ + } \ + BLI_array_empty(arr1); \ + for (i = 0; i < BLI_array_count(arr2); i++) { \ + BLI_array_append(arr1, arr2[i]); \ + } \ + BLI_array_empty(arr2); \ + for (i = 0; i < BLI_array_count(arr_tmp); i++) { \ + BLI_array_append(arr2, arr_tmp[i]); \ + } \ + BLI_array_free(arr_tmp); \ + } + +void bmesh_bridge_loops_exec(BMesh *bm, BMOperator *op) +{ + BMEdge **ee1 = NULL, **ee2 = NULL; + BMVert **vv1 = NULL, **vv2 = NULL; + BLI_array_declare(ee1); + BLI_array_declare(ee2); + BLI_array_declare(vv1); + BLI_array_declare(vv2); + BMOIter siter; + BMIter iter; + BMEdge *e, *nexte; + int c = 0, cl1 = 0, cl2 = 0; + + BMO_slot_buffer_flag_enable(bm, op, "edges", EDGE_MARK, BM_EDGE); + + BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) { + if (!BMO_elem_flag_test(bm, e, EDGE_DONE)) { + BMVert *v, *ov; + /* BMEdge *e2, *e3, *oe = e; */ /* UNUSED */ + BMEdge *e2, *e3; + + if (c > 2) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Select only two edge loops"); + goto cleanup; + } + + e2 = e; + v = e->v1; + do { + v = BM_edge_other_vert(e2, v); + nexte = NULL; + BM_ITER(e3, &iter, bm, BM_EDGES_OF_VERT, v) { + if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK)) { + if (nexte == NULL) { + nexte = e3; + } + else { + /* edges do not form a loop: there is a disk + * with more than two marked edges. */ + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Selection must only contain edges from two edge loops"); + goto cleanup; + } + } + } + + if (nexte) + e2 = nexte; + } while (nexte && e2 != e); + + if (!e2) + e2 = e; + + e = e2; + ov = v; + do { + if (c == 0) { + BLI_array_append(ee1, e2); + BLI_array_append(vv1, v); + } + else { + BLI_array_append(ee2, e2); + BLI_array_append(vv2, v); + } + + BMO_elem_flag_enable(bm, e2, EDGE_DONE); + + v = BM_edge_other_vert(e2, v); + BM_ITER(e3, &iter, bm, BM_EDGES_OF_VERT, v) { + if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK) && !BMO_elem_flag_test(bm, e3, EDGE_DONE)) { + break; + } + } + if (e3) + e2 = e3; + } while (e3 && e2 != e); + + if (v && !e3) { + if (c == 0) { + if (BLI_array_count(vv1) && v == vv1[BLI_array_count(vv1) - 1]) { + printf("%s: internal state waning *TODO DESCRIPTION!*\n", __func__); + } + BLI_array_append(vv1, v); + } + else { + BLI_array_append(vv2, v); + } + } + + /* test for connected loops, and set cl1 or cl2 if so */ + if (v == ov) { + if (c == 0) { + cl1 = 1; + } + else { + cl2 = 1; + } + } + + c++; + } + } + + if (ee1 && ee2) { + int i, j; + BMVert *v1, *v2, *v3, *v4; + int starti = 0, dir1 = 1, wdir = 0, lenv1, lenv2; + + /* Simplify code below by avoiding the (!cl1 && cl2) case */ + if (!cl1 && cl2) { + SWAP(int, cl1, cl2); + ARRAY_SWAP(BMVert *, vv1, vv2); + ARRAY_SWAP(BMEdge *, ee1, ee2); + } + + lenv1 = lenv2 = BLI_array_count(vv1); + + /* Below code assumes vv1/vv2 each have at least two verts. should always be + * a safe assumption, since ee1/ee2 are non-empty and an edge has two verts. */ + BLI_assert((lenv1 > 1) && (lenv2 > 1)); + + /* BMESH_TODO: Would be nice to handle cases where the edge loops + * have different edge counts by generating triangles & quads for + * the bridge instead of quads only. */ + if (BLI_array_count(ee1) != BLI_array_count(ee2)) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Selected loops must have equal edge counts"); + goto cleanup; + } + + j = 0; + if (vv1[0] == vv1[lenv1 - 1]) { + lenv1--; + } + if (vv2[0] == vv2[lenv2 - 1]) { + lenv2--; + } + + /* Find starting point and winding direction for two unclosed loops */ + if (!cl1 && !cl2) { + /* First point of loop 1 */ + v1 = get_outer_vert(bm, ee1[0]); + /* Last point of loop 1 */ + v2 = get_outer_vert(bm, ee1[clamp_index(-1, BLI_array_count(ee1))]); + /* First point of loop 2 */ + v3 = get_outer_vert(bm, ee2[0]); + /* Last point of loop 2 */ + v4 = get_outer_vert(bm, ee2[clamp_index(-1, BLI_array_count(ee2))]); + + /* If v1 is a better match for v4 than v3, AND v2 is a better match + * for v3 than v4, the loops are in opposite directions, so reverse + * the order of reads from vv1. We can avoid sqrt for comparison */ + if (len_squared_v3v3(v1->co, v3->co) > len_squared_v3v3(v1->co, v4->co) && + len_squared_v3v3(v2->co, v4->co) > len_squared_v3v3(v2->co, v3->co)) + { + dir1 = -1; + starti = clamp_index(-1, lenv1); + } + } + + /* Find the shortest distance from a vert in vv1 to vv2[0]. Use that + * vertex in vv1 as a starting point in the first loop, while starting + * from vv2[0] in the second loop. This is a simplistic attempt to get + * a better edge-to-edge match between the two loops. */ + if (cl1) { + int previ, nexti; + float min = 1e32; + + /* BMESH_TODO: Would be nice to do a more thorough analysis of all + * the vertices in both loops to find a more accurate match for the + * starting point and winding direction of the bridge generation. */ + + for (i = 0; i < BLI_array_count(vv1); i++) { + if (len_v3v3(vv1[i]->co, vv2[0]->co) < min) { + min = len_v3v3(vv1[i]->co, vv2[0]->co); + starti = i; + } + } + + /* Reverse iteration order for the first loop if the distance of + * the (starti - 1) vert from vv1 is a better match for vv2[1] than + * the (starti + 1) vert. + * + * This is not always going to be right, but it will work better in + * the average case. + */ + previ = clamp_index(starti - 1, lenv1); + nexti = clamp_index(starti + 1, lenv1); + + /* avoid sqrt for comparison */ + if (len_squared_v3v3(vv1[nexti]->co, vv2[1]->co) > len_squared_v3v3(vv1[previ]->co, vv2[1]->co)) { + /* reverse direction for reading vv1 (1 is forward, -1 is backward) */ + dir1 = -1; + } + } + + /* Vert rough attempt to determine proper winding for the bridge quads: + * just uses the first loop it finds for any of the edges of ee2 or ee1 */ + if (wdir == 0) { + for (i = 0; i < BLI_array_count(ee2); i++) { + if (ee2[i]->l) { + wdir = (ee2[i]->l->v == vv2[i]) ? (-1) : (1); + break; + } + } + } + if (wdir == 0) { + for (i = 0; i < BLI_array_count(ee1); i++) { + j = clamp_index((i * dir1) + starti, BLI_array_count(ee1)); + if (ee1[j]->l && ee2[j]->l) { + wdir = (ee2[j]->l->v == vv2[j]) ? (1) : (-1); + break; + } + } + } + + /* Generate the bridge quads */ + for (i = 0; i < BLI_array_count(ee1) && i < BLI_array_count(ee2); i++) { + BMFace *f; + int i1, i1next, i2, i2next; + + i1 = clamp_index(i * dir1 + starti, lenv1); + i1next = clamp_index((i + 1) * dir1 + starti, lenv1); + i2 = i; + i2next = clamp_index(i + 1, lenv2); + + if (vv1[i1] == vv1[i1next]) { + continue; + } + + if (wdir < 0) { + SWAP(int, i1, i1next); + SWAP(int, i2, i2next); + } + + f = BM_face_create_quad_tri(bm, + vv1[i1], + vv2[i2], + vv2[i2next], + vv1[i1next], + NULL, TRUE); + if (!f || f->len != 4) { + fprintf(stderr, "%s: in bridge! (bmesh internal error)\n", __func__); + } + } + } + +cleanup: + BLI_array_free(ee1); + BLI_array_free(ee2); + BLI_array_free(vv1); + BLI_array_free(vv2); +} -- cgit v1.2.3