From 55f929ab3d01eb885904e37eee8fbb254fe53d1c Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 11 May 2013 14:40:03 +0000 Subject: - add generic edge-loop utility functions for bmesh. - rewrite bridge tool to use the new functions (using edge & vertex arrays was quite cumbersome). --- source/blender/bmesh/CMakeLists.txt | 3 + source/blender/bmesh/bmesh.h | 1 + source/blender/bmesh/intern/bmesh_edgeloop.c | 300 +++++++++++++++++++ source/blender/bmesh/intern/bmesh_edgeloop.h | 57 ++++ source/blender/bmesh/operators/bmo_bridge.c | 325 ++++++++++++++++++++ source/blender/bmesh/operators/bmo_connect.c | 426 --------------------------- 6 files changed, 686 insertions(+), 426 deletions(-) create mode 100644 source/blender/bmesh/intern/bmesh_edgeloop.c create mode 100644 source/blender/bmesh/intern/bmesh_edgeloop.h create mode 100644 source/blender/bmesh/operators/bmo_bridge.c (limited to 'source') diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index 472f7d2d8f0..dd8bb22727c 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -41,6 +41,7 @@ set(INC_SYS set(SRC operators/bmo_beautify.c operators/bmo_bevel.c + operators/bmo_bridge.c operators/bmo_connect.c operators/bmo_create.c operators/bmo_dissolve.c @@ -70,6 +71,8 @@ set(SRC intern/bmesh_construct.h intern/bmesh_core.c intern/bmesh_core.h + intern/bmesh_edgeloop.c + intern/bmesh_edgeloop.h intern/bmesh_inline.h intern/bmesh_interp.c intern/bmesh_interp.h diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h index cfd30f29541..de78e192ebb 100644 --- a/source/blender/bmesh/bmesh.h +++ b/source/blender/bmesh/bmesh.h @@ -253,6 +253,7 @@ extern "C" { #include "intern/bmesh_construct.h" #include "intern/bmesh_core.h" +#include "intern/bmesh_edgeloop.h" #include "intern/bmesh_interp.h" #include "intern/bmesh_iterators.h" #include "intern/bmesh_log.h" diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c new file mode 100644 index 00000000000..ce2a80c6cfc --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_edgeloop.c @@ -0,0 +1,300 @@ +/* + * ***** 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. + * + * The Original Code is Copyright (C) 2013 by Campbell Barton. + * All rights reserved. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/intern/bmesh_edgeloop.c + * \ingroup bmesh + * + * Generic utility functions for getting edge loops from a mesh. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_math_vector.h" +#include "BLI_listbase.h" + +#include "bmesh.h" + +#include "bmesh_edgeloop.h" /* own include */ + +typedef struct BMEdgeLoopStore { + struct BMEdgeLoopStore *next, *prev; + ListBase verts; + int flag; + int len; + /* optional values to calc */ + float co[3], no[3]; +} BMEdgeLoopStore; + +#define BM_EDGELOOP_IS_CLOSED (1 << 0) + +static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, + BMEdge **r_e) +{ + BMIter iter; + BMEdge *e, *e_next; + unsigned int count = 0; + + BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (v_other != v_prev) { + e_next = e; + count++; + } + } + } + + *r_e = e_next; + return count; +} + +/** + * \return success + */ +static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, int dir) +{ + void (*add_fn)(ListBase *, void *) = dir == 1 ? BLI_addhead : BLI_addtail; + BMEdge *e_next; + BMVert *v_next; + BMVert *v_first = v; + + BLI_assert(ABS(dir) == 1); + + if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) { + return true; + } + + while (v) { + LinkData *node = MEM_callocN(sizeof(*node), __func__); + int count; + node->data = v; + add_fn(&el_store->verts, node); + el_store->len++; + BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG); + + count = bm_vert_other_tag(v, v_prev, &e_next); + if (count == 1) { + v_next = BM_edge_other_vert(e_next, v); + BM_elem_flag_disable(e_next, BM_ELEM_INTERNAL_TAG); + if (UNLIKELY(v_next == v_first)) { + el_store->flag |= BM_EDGELOOP_IS_CLOSED; + v_next = NULL; + } + } + else if (count == 0) { + /* pass */ + v_next = NULL; + } + else { + v_next = NULL; + return false; + } + + v_prev = v; + v = v_next; + } + + return true; +} + +/** + * \return listbase of listbases, each linking to a vertex. + */ +int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data) +{ + BMIter iter; + BMEdge *e; + BMVert *v; + int count = 0; + + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG); + } + + /* first flush edges to tags, and tag verts */ + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (test_fn(e, user_data)) { + BM_elem_flag_enable(e, BM_ELEM_INTERNAL_TAG); + BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG); + BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG); + } + else { + BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG); + } + } + + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) { + BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__); + + /* add both directions */ + if (bm_loop_build(el_store, e->v1, e->v2, 1) && + bm_loop_build(el_store, e->v2, e->v1, -1)) + { + BLI_addtail(r_eloops, el_store); + BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG); + count++; + } + else { + BM_edgeloop_free(r_eloops, el_store); + } + } + } + return count; +} + +void BM_mesh_edgeloops_free(ListBase *eloops) +{ + BMEdgeLoopStore *el_store; + while ((el_store = eloops->first)) { + BM_edgeloop_free(eloops, el_store); + } +} + +void BM_mesh_edgeloops_calc_center(BMesh *bm, ListBase *eloops) +{ + BMEdgeLoopStore *el_store; + for (el_store = eloops->first; el_store; el_store = el_store->next) { + BM_edgeloop_calc_center(bm, el_store); + } +} + +void BM_mesh_edgeloops_calc_normal(BMesh *bm, ListBase *eloops) +{ + BMEdgeLoopStore *el_store; + for (el_store = eloops->first; el_store; el_store = el_store->next) { + BM_edgeloop_calc_normal(bm, el_store); + } +} + +/* -------------------------------------------------------------------- */ +/* BM_edgeloop_*** functions */ + +void BM_edgeloop_free(ListBase *eloops, BMEdgeLoopStore *el_store) +{ + BLI_freelistN(&el_store->verts); + BLI_remlink(eloops, el_store); + MEM_freeN(el_store); +} + +bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store) +{ + return (el_store->flag & BM_EDGELOOP_IS_CLOSED) != 0; +} + +ListBase *BM_edgeloop_verts_get(BMEdgeLoopStore *el_store) +{ + return &el_store->verts; +} + +int BM_edgeloop_length_get(BMEdgeLoopStore *el_store) +{ + return el_store->len; +} + +const float *BM_edgeloop_normal_get(struct BMEdgeLoopStore *el_store) +{ + return el_store->no; +} + +const float *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store) +{ + return el_store->co; +} + + +#define NODE_AS_CO(n) ((BMVert *)((LinkData *)n)->data)->co + +void BM_edgeloop_calc_center(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store) +{ + LinkData *node_curr = el_store->verts.last; + LinkData *node_prev = ((LinkData *)el_store->verts.last)->prev; + LinkData *node_first = el_store->verts.first; + LinkData *node_next = node_first; + + float const *v_prev = NODE_AS_CO(node_prev); + float const *v_curr = NODE_AS_CO(node_curr); + float const *v_next = NODE_AS_CO(node_next); + + float totw = 0.0f; + float w_prev; + + zero_v3(el_store->co); + + w_prev = len_v3v3(v_prev, v_curr); + do { + const float w_curr = len_v3v3(v_curr, v_next); + const float w = (w_curr + w_prev); + madd_v3_v3fl(el_store->co, v_curr, w); + totw += w; + w_prev = w_curr; + + + node_prev = node_curr; + node_curr = node_next; + node_next = node_next->next; + + if (node_next == NULL) { + break; + } + v_prev = v_curr; + v_curr = v_next; + v_next = NODE_AS_CO(node_next); + } while (1); + + if (totw != 0.0f) + mul_v3_fl(el_store->co, 1.0f / (float) totw); + +} + +void BM_edgeloop_calc_normal(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store) +{ + LinkData *node_curr = el_store->verts.first; + float const *v_prev = NODE_AS_CO(el_store->verts.last); + float const *v_curr = NODE_AS_CO(node_curr); + + /* Newell's Method */ + do { + add_newell_cross_v3_v3v3(el_store->no, v_prev, v_curr); + + if ((node_curr = node_curr->next)) { + v_prev = v_curr; + v_curr = NODE_AS_CO(node_curr); + } + else { + break; + } + } while (true); + + if (UNLIKELY(normalize_v3(el_store->no) == 0.0f)) { + el_store->no[2] = 1.0f; /* other axis set to 0.0 */ + } +} + + +void BM_edgeloop_flip(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store) +{ + negate_v3(el_store->no); + BLI_reverselist(&el_store->verts); +} diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.h b/source/blender/bmesh/intern/bmesh_edgeloop.h new file mode 100644 index 00000000000..06a457c3dd6 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_edgeloop.h @@ -0,0 +1,57 @@ +/* + * ***** 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. + * + * The Original Code is Copyright (C) 2013 by Campbell Barton. + * All rights reserved. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BMESH_EDGELOOP_H__ +#define __BMESH_EDGELOOP_H__ + +/** \file blender/bmesh/intern/bmesh_edgeloop.h + * \ingroup bmesh + */ + +struct ListBase; +struct BMEdgeLoopStore; + +/* multiple edgeloops (ListBase) */ +int BM_mesh_edgeloops_find(BMesh *bm, struct ListBase *r_lb, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data); + +void BM_mesh_edgeloops_free(struct ListBase *eloops); +void BM_mesh_edgeloops_calc_center(BMesh *bm, struct ListBase *eloops); +void BM_mesh_edgeloops_calc_normal(BMesh *bm, struct ListBase *eloops); + + +/* single edgeloop */ +void BM_edgeloop_free(struct ListBase *eloops, struct BMEdgeLoopStore *el_store); +bool BM_edgeloop_is_closed(struct BMEdgeLoopStore *el_store); +int BM_edgeloop_length_get(struct BMEdgeLoopStore *el_store); +struct ListBase *BM_edgeloop_verts_get(struct BMEdgeLoopStore *el_store); +const float *BM_edgeloop_normal_get(struct BMEdgeLoopStore *el_store); +const float *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store); +void BM_edgeloop_calc_center(BMesh *bm, struct BMEdgeLoopStore *el_store); +void BM_edgeloop_calc_normal(BMesh *bm, struct BMEdgeLoopStore *el_store); +void BM_edgeloop_flip(BMesh *bm, struct BMEdgeLoopStore *el_store); + +#define BM_EDGELOOP_NEXT(el_store, elink) \ + (elink)->next ? elink->next : (BM_edgeloop_is_closed(el_store) ? BM_edgeloop_verts_get(el_store)->first : NULL) + +#endif /* __BMESH_EDGELOOP_H__ */ diff --git a/source/blender/bmesh/operators/bmo_bridge.c b/source/blender/bmesh/operators/bmo_bridge.c new file mode 100644 index 00000000000..a9201fb8de5 --- /dev/null +++ b/source/blender/bmesh/operators/bmo_bridge.c @@ -0,0 +1,325 @@ +/* + * ***** 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, Campbell Barton + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/operators/bmo_bridge.c + * \ingroup bmesh + * + * Connect verts across faces (splits faces) and bridge tool. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_math.h" +#include "BLI_utildefines.h" +#include "BLI_listbase.h" + +#include "bmesh.h" + +#include "intern/bmesh_operators_private.h" /* own include */ + +#define EDGE_MARK 4 +#define FACE_OUT 16 + +/* get the 2 loops matching 2 verts. + * first attempt to get the face corners that use the edge defined by v1 & v2, + * if that fails just get any loop thats on the vert (the first one) */ +static void bm_vert_loop_pair(BMesh *bm, BMVert *v1, BMVert *v2, BMLoop **l1, BMLoop **l2) +{ + BMIter liter; + BMLoop *l; + + if ((v1->e && v1->e->l) && + (v2->e && v2->e->l)) + { + BM_ITER_ELEM (l, &liter, v1, BM_LOOPS_OF_VERT) { + if (l->prev->v == v2) { + *l1 = l; + *l2 = l->prev; + return; + } + else if (l->next->v == v2) { + *l1 = l; + *l2 = l->next; + return; + } + } + } + + /* fallback to _any_ loop */ + *l1 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v1, 0); + *l2 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v2, 0); +} + +/* el_b can have any offset */ +static float bm_edgeloop_offset_length(LinkData *el_a, LinkData *el_b, + LinkData *el_b_first, const float len_max) +{ + float len = 0.0f; + BLI_assert(el_a->prev == NULL); /* must be first */ + do { + len += len_v3v3(((BMVert *)el_a->data)->co, ((BMVert *)el_b->data)->co); + } while ((el_b = el_b->next ? el_b->next : el_b_first), + (el_a = el_a->next) && (len < len_max)); + return len; +} + +static void bm_bridge_best_rotation(struct BMEdgeLoopStore *el_store_a, struct BMEdgeLoopStore *el_store_b) +{ + ListBase *lb_a = BM_edgeloop_verts_get(el_store_a); + ListBase *lb_b = BM_edgeloop_verts_get(el_store_b); + LinkData *el_a = lb_a->first; + LinkData *el_b = lb_b->first; + LinkData *el_b_first = el_b; + LinkData *el_b_best = NULL; + + float len_best = FLT_MAX; + + for (; el_b; el_b = el_b->next) { + const float len = bm_edgeloop_offset_length(el_a, el_b, el_b_first, len_best); + if (len < len_best) { + el_b_best = el_b; + len_best = len; + } + } + + if (el_b_best) { + BLI_rotatelist(lb_b, el_b_best); + } +} + +static bool bm_edge_test_cb(BMEdge *e, void *bm_v) +{ + return BMO_elem_flag_test((BMesh *)bm_v, e, EDGE_MARK); +} + +static void bridge_loop_pair(BMesh *bm, + struct BMEdgeLoopStore *el_store_a, + struct BMEdgeLoopStore *el_store_b, + const bool use_merge, const float merge_factor) +{ + LinkData *el_a_first, *el_b_first; + const bool is_closed = BM_edgeloop_is_closed(el_store_a) && BM_edgeloop_is_closed(el_store_b); + + if (dot_v3v3(BM_edgeloop_normal_get(el_store_a), BM_edgeloop_normal_get(el_store_b)) < 0.0f) { + BM_edgeloop_flip(bm, el_store_b); + } + + /* we only care about flipping if we make faces */ + if (use_merge == false) { + float no[3]; + float dir[3]; + + add_v3_v3v3(no, BM_edgeloop_normal_get(el_store_a), BM_edgeloop_normal_get(el_store_b)); + sub_v3_v3v3(dir, BM_edgeloop_center_get(el_store_a), BM_edgeloop_center_get(el_store_b)); + + if (dot_v3v3(no, dir) < 0.0f) { + BM_edgeloop_flip(bm, el_store_a); + BM_edgeloop_flip(bm, el_store_b); + } + + /* vote on winding (so new face winding is based on existing connected faces) */ + if (bm->totface) { + struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b}; + int i = 0; + int winding_votes = 0; + int winding_dir = 1; + for (i = 0; i < 2; i++, winding_dir = -winding_dir) { + LinkData *el; + for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) { + LinkData *el_next = BM_EDGELOOP_NEXT(estore_pair[i], el); + BMEdge *e = BM_edge_exists(el->data, el_next->data); + if (e && BM_edge_is_boundary(e)) { + winding_votes += ((e->l->v == el->data) ? winding_dir : -winding_dir); + } + } + } + + if (winding_votes < 0) { + BM_edgeloop_flip(bm, el_store_a); + BM_edgeloop_flip(bm, el_store_b); + } + } + } + + if (is_closed) { + bm_bridge_best_rotation(el_store_a, el_store_b); + } + + /* Assign after flipping is finalized */ + el_a_first = BM_edgeloop_verts_get(el_store_a)->first; + el_b_first = BM_edgeloop_verts_get(el_store_b)->first; + + + if (use_merge) { + LinkData *el_a; + LinkData *el_b; + const int vert_len = BM_edgeloop_length_get(el_store_a); + const int edge_len = is_closed ? vert_len : vert_len - 1; + BMEdge **earr_a = MEM_mallocN(sizeof(*earr_a) * vert_len, __func__); + BMEdge **earr_b = MEM_mallocN(sizeof(*earr_b) * vert_len, __func__); + int i; + + el_a = el_a_first; + el_b = el_b_first; + + /* first get the edges in order (before splicing verts) */ + for (i = 0; i < vert_len; i++) { + LinkData *el_a_next = BM_EDGELOOP_NEXT(el_store_a, el_a); + LinkData *el_b_next = BM_EDGELOOP_NEXT(el_store_b, el_b); + + /* last edge will be NULL for non closed loops */ + earr_a[i] = BM_edge_exists(el_a->data, el_a_next->data); + earr_b[i] = BM_edge_exists(el_b->data, el_b_next->data); + + el_a = el_a_next; + el_b = el_b_next; + } + + el_a = el_a_first; + el_b = el_b_first; + for (i = 0; i < vert_len; i++) { + BMVert *v_a = el_a->data, *v_b = el_b->data; + BM_data_interp_from_verts(bm, v_a, v_b, v_b, merge_factor); + interp_v3_v3v3(v_b->co, v_a->co, v_b->co, merge_factor); + BM_elem_flag_merge(v_a, v_b); + BM_vert_splice(bm, v_a, v_b); + + el_a = el_a->next; + el_b = el_b->next; + } + for (i = 0; i < edge_len; i++) { + BMEdge *e1 = earr_a[i]; + BMEdge *e2 = earr_b[i]; + BM_data_interp_from_edges(bm, e1, e2, e2, merge_factor); + BM_elem_flag_merge(e1, e2); + BM_edge_splice(bm, e1, e2); + } + + MEM_freeN(earr_a); + MEM_freeN(earr_b); + } + else { + LinkData *el_a = el_a_first; + LinkData *el_b = el_b_first; + + LinkData *el_a_next; + LinkData *el_b_next; + + + while (true) { + BMFace *f, *f_example; + BMLoop *l_iter; + BMVert *v_a, *v_b, *v_a_next, *v_b_next; + + BMLoop *l_1 = NULL; + BMLoop *l_2 = NULL; + BMLoop *l_1_next = NULL; + BMLoop *l_2_next = NULL; + + if (is_closed) { + el_a_next = BM_EDGELOOP_NEXT(el_store_a, el_a); + el_b_next = BM_EDGELOOP_NEXT(el_store_b, el_b); + } + else { + el_a_next = el_a->next; + el_b_next = el_b->next; + if (ELEM(NULL, el_a_next, el_b_next)) { + break; + } + } + + v_a = el_a->data; + v_b = el_b->data; + v_a_next = el_a_next->data; + v_b_next = el_b_next->data; + + /* get loop data - before making the face */ + bm_vert_loop_pair(bm, v_a, v_b, &l_1, &l_2); + bm_vert_loop_pair(bm, v_a_next, v_b_next, &l_1_next, &l_2_next); + /* copy if loop data if its is missing on one ring */ + if (l_1 && l_1_next == NULL) l_1_next = l_1; + if (l_1_next && l_1 == NULL) l_1 = l_1_next; + if (l_2 && l_2_next == NULL) l_2_next = l_2; + if (l_2_next && l_2 == NULL) l_2 = l_2_next; + f_example = l_1 ? l_1->f : (l_2 ? l_2->f : NULL); + + f = BM_face_create_quad_tri(bm, + el_a->data, + el_b->data, + el_b_next->data, + el_a_next->data, + f_example, true); + BMO_elem_flag_enable(bm, f, FACE_OUT); + if (el_a_next == el_a_first) { + break; + } + + l_iter = BM_FACE_FIRST_LOOP(f); + + if (l_1) BM_elem_attrs_copy(bm, bm, l_1, l_iter); l_iter = l_iter->next; + if (l_2) BM_elem_attrs_copy(bm, bm, l_2, l_iter); l_iter = l_iter->next; + if (l_2_next) BM_elem_attrs_copy(bm, bm, l_2_next, l_iter); l_iter = l_iter->next; + if (l_1_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter); + + el_a = el_a_next; + el_b = el_b_next; + } + } +} + +void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op) +{ + ListBase eloops = {NULL}; + + /* merge-bridge support */ + const bool use_merge = BMO_slot_bool_get(op->slots_in, "use_merge"); + const float merge_factor = BMO_slot_float_get(op->slots_in, "merge_factor"); + int count; + bool change = false; + + BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK); + + count = BM_mesh_edgeloops_find(bm, &eloops, bm_edge_test_cb, bm); + + BM_mesh_edgeloops_calc_normal(bm, &eloops); + BM_mesh_edgeloops_calc_center(bm, &eloops); + + if ((count == 2) && (BM_edgeloop_length_get(eloops.first) == BM_edgeloop_length_get(eloops.last))) { + bridge_loop_pair(bm, eloops.first, eloops.last, use_merge, merge_factor); + change = true; + + } + else if (count == 2) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Selected loops must have equal edge counts"); + } + else { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Select only two edge loops"); + } + + BM_mesh_edgeloops_free(&eloops); + + if (change) { + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT); + } +} diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c index f19d4c06931..0c62330fc24 100644 --- a/source/blender/bmesh/operators/bmo_connect.c +++ b/source/blender/bmesh/operators/bmo_connect.c @@ -39,9 +39,6 @@ #define VERT_INPUT 1 #define EDGE_OUT 1 #define FACE_NEW 2 -#define EDGE_MARK 4 -#define EDGE_DONE 8 -#define FACE_OUT 16 void bmo_connect_verts_exec(BMesh *bm, BMOperator *op) { @@ -126,426 +123,3 @@ void bmo_connect_verts_exec(BMesh *bm, BMOperator *op) BLI_array_free(loops_split); BLI_array_free(verts_pair); } - -static BMVert *get_outer_vert(BMesh *bm, BMEdge *e) -{ - BMIter iter; - BMEdge *e2; - int i; - - i = 0; - BM_ITER_ELEM (e2, &iter, e->v1, BM_EDGES_OF_VERT) { - 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) -{ - if (x >= 0) { - return x % len; - } - else { - int r = len - (-x % len); - if (r == len) - return len - 1; - else - return r; - } -} - -/* 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)0 - -/* get the 2 loops matching 2 verts. - * first attempt to get the face corners that use the edge defined by v1 & v2, - * if that fails just get any loop thats on the vert (the first one) */ -static void bm_vert_loop_pair(BMesh *bm, BMVert *v1, BMVert *v2, BMLoop **l1, BMLoop **l2) -{ - BMIter liter; - BMLoop *l; - - if ((v1->e && v1->e->l) && - (v2->e && v2->e->l)) - { - BM_ITER_ELEM (l, &liter, v1, BM_LOOPS_OF_VERT) { - if (l->prev->v == v2) { - *l1 = l; - *l2 = l->prev; - return; - } - else if (l->next->v == v2) { - *l1 = l; - *l2 = l->next; - return; - } - } - } - - /* fallback to _any_ loop */ - *l1 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v1, 0); - *l2 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v2, 0); -} - -void bmo_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; - - /* merge-bridge support */ - const bool use_merge = BMO_slot_bool_get(op->slots_in, "use_merge"); - const float merge_factor = BMO_slot_float_get(op->slots_in, "merge_factor"); - - BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK); - - BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) { - if (!BMO_elem_flag_test(bm, e, EDGE_DONE)) { - BMVert *v, *v_old; - /* BMEdge *e2, *e3, *e_old = 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_ELEM (e3, &iter, v, BM_EDGES_OF_VERT) { - 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; - v_old = 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_ELEM (e3, &iter, v, BM_EDGES_OF_VERT) { - 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 == v_old) { - 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; - } - - 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))]); - - /* ugh, happens when bridging single edges, user could just make a face - * but better support it for sake of completeness */ - if (v1 == v2) { - BLI_assert(BLI_array_count(ee1) == 1); - v2 = (vv1[0] == v2) ? vv1[1] : vv1[0]; - } - if (v3 == v4) { - BLI_assert(BLI_array_count(ee2) == 1); - v4 = (vv2[0] == v4) ? vv2[1] : vv2[0]; - } - - /* 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 smallest sum of distances from verts in vv1 to verts in vv2, - * finding a starting point in the first loop, to start with vv2[0] in the - * second loop. This is a simplistic attempt to get a better edge-to-edge - * match between two loops. */ - if (cl1) { - float min = 1e32; - - for (i = 0; i < lenv1; i++) { - float len; - - /* compute summed length between vertices in forward direction */ - len = 0.0f; - for (j = 0; (j < lenv2) && (len < min); j++) { - len += len_v3v3(vv1[clamp_index(i + j, lenv1)]->co, vv2[j]->co); - } - - if (len < min) { - min = len; - starti = i; - dir1 = 1; - } - - /* compute summed length between vertices in backward direction */ - len = 0.0f; - for (j = 0; (j < lenv2) && (len < min); j++) { - len += len_v3v3(vv1[clamp_index(i - j, lenv1)]->co, vv2[j]->co); - } - - if (len < min) { - min = len; - starti = i; - dir1 = -1; - } - } - } - - if (use_merge == false) { - /* 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; - } - } - } - } - -#define EDGE_ORD_VERTS_NEXT { \ - 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; \ - } (void)0 - -#define EDGE_ORD_VERTS { \ - i1 = clamp_index(i * dir1 + starti, lenv1); \ - i2 = i; \ - } (void)0 - - /* merge loops of bridge faces */ - if (use_merge) { - const int vert_len = min_ii(BLI_array_count(vv1), BLI_array_count(vv2)) - ((cl1 || cl2) ? 1 : 0); - const int edge_len = min_ii(BLI_array_count(ee1), BLI_array_count(ee2)); - - /* first get the edges in order (before splicing verts) */ - for (i = 0; i < vert_len; i++) { - int i1, i1next, i2, i2next; - EDGE_ORD_VERTS_NEXT; - - ee1[i] = BM_edge_exists(vv1[i1], vv1[i1next]); - ee2[i] = BM_edge_exists(vv2[i2], vv2[i2next]); - } - for (i = 0; i < vert_len; i++) { - int i1, i2; - EDGE_ORD_VERTS; - - BM_data_interp_from_verts(bm, vv1[i1], vv2[i2], vv2[i2], merge_factor); - interp_v3_v3v3(vv2[i2]->co, vv1[i1]->co, vv2[i2]->co, merge_factor); - BM_elem_flag_merge(vv1[i1], vv2[i2]); - BM_vert_splice(bm, vv1[i1], vv2[i2]); - } - for (i = 0; i < edge_len; i++) { - BMEdge *e1 = ee1[i]; - BMEdge *e2 = ee2[i]; - BM_data_interp_from_edges(bm, e1, e2, e2, merge_factor); - BM_elem_flag_merge(e1, e2); - BM_edge_splice(bm, e1, e2); - } - } - else { - /* Generate the bridge quads */ - for (i = 0; i < BLI_array_count(ee1) && i < BLI_array_count(ee2); i++) { - BMFace *f; - - BMLoop *l_1 = NULL; - BMLoop *l_2 = NULL; - BMLoop *l_1_next = NULL; - BMLoop *l_2_next = NULL; - BMLoop *l_iter; - BMFace *f_example; - - int i1, i1next, i2, i2next; - - EDGE_ORD_VERTS_NEXT; - - if (wdir < 0) { - SWAP(int, i1, i1next); - SWAP(int, i2, i2next); - } - - /* get loop data - before making the face */ - bm_vert_loop_pair(bm, vv1[i1], vv2[i2], &l_1, &l_2); - bm_vert_loop_pair(bm, vv1[i1next], vv2[i2next], &l_1_next, &l_2_next); - /* copy if loop data if its is missing on one ring */ - if (l_1 && l_1_next == NULL) l_1_next = l_1; - if (l_1_next && l_1 == NULL) l_1 = l_1_next; - if (l_2 && l_2_next == NULL) l_2_next = l_2; - if (l_2_next && l_2 == NULL) l_2 = l_2_next; - f_example = l_1 ? l_1->f : (l_2 ? l_2->f : NULL); - - f = BM_face_create_quad_tri(bm, - vv1[i1], - vv2[i2], - vv2[i2next], - vv1[i1next], - f_example, true); - if (UNLIKELY((f == NULL) || (f->len != 4))) { - fprintf(stderr, "%s: in bridge! (bmesh internal error)\n", __func__); - } - else { - BMO_elem_flag_enable(bm, f, FACE_OUT); - - l_iter = BM_FACE_FIRST_LOOP(f); - - if (l_1) BM_elem_attrs_copy(bm, bm, l_1, l_iter); l_iter = l_iter->next; - if (l_2) BM_elem_attrs_copy(bm, bm, l_2, l_iter); l_iter = l_iter->next; - if (l_2_next) BM_elem_attrs_copy(bm, bm, l_2_next, l_iter); l_iter = l_iter->next; - if (l_1_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter); - } - } - } - } - -#undef EDGE_ORD_VERTS_NEXT -#undef EDGE_ORD_VERTS - - BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT); - -cleanup: - BLI_array_free(ee1); - BLI_array_free(ee2); - BLI_array_free(vv1); - BLI_array_free(vv2); -} -- cgit v1.2.3