2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 * Connect verts across faces (splits faces).
23 #include "BLI_alloca.h"
24 #include "BLI_linklist_stack.h"
25 #include "BLI_utildefines.h"
26 #include "BLI_utildefines_stack.h"
30 #include "intern/bmesh_operators_private.h" /* own include */
35 /* Edge spans 2 VERT_INPUT's, its a nop,
36 * but include in "edges.out" */
37 #define EDGE_OUT_ADJ 2
40 #define FACE_EXCLUDE 4
42 static int bm_face_connect_verts(BMesh *bm, BMFace *f, const bool check_degenerate)
44 const uint pair_split_max = f->len / 2;
45 BMLoop *(*loops_split)[2] = BLI_array_alloca(loops_split, pair_split_max);
46 STACK_DECLARE(loops_split);
47 BMVert *(*verts_pair)[2] = BLI_array_alloca(verts_pair, pair_split_max);
48 STACK_DECLARE(verts_pair);
50 BMLoop *l_tag_prev = NULL, *l_tag_first = NULL;
51 BMLoop *l_iter, *l_first;
55 STACK_INIT(loops_split, pair_split_max);
56 STACK_INIT(verts_pair, pair_split_max);
58 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
60 if (BMO_vert_flag_test(bm, l_iter->v, VERT_INPUT) &&
61 /* ensure this vertex isnt part of a contiguous group */
62 ((BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT) == 0) ||
63 (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT) == 0))) {
65 l_tag_prev = l_tag_first = l_iter;
69 if (!BM_loop_is_adjacent(l_tag_prev, l_iter)) {
71 e = BM_edge_exists(l_tag_prev->v, l_iter->v);
72 if (e == NULL || !BMO_edge_flag_test(bm, e, EDGE_OUT)) {
73 BMLoop **l_pair = STACK_PUSH_RET(loops_split);
74 l_pair[0] = l_tag_prev;
81 } while ((l_iter = l_iter->next) != l_first);
83 if (STACK_SIZE(loops_split) == 0) {
87 if (!BM_loop_is_adjacent(l_tag_first, l_tag_prev) &&
88 /* ensure we don't add the same pair twice */
89 (((loops_split[0][0] == l_tag_first) && (loops_split[0][1] == l_tag_prev)) == 0)) {
90 BMLoop **l_pair = STACK_PUSH_RET(loops_split);
91 l_pair[0] = l_tag_first;
92 l_pair[1] = l_tag_prev;
95 if (check_degenerate) {
96 BM_face_splits_check_legal(bm, f, loops_split, STACK_SIZE(loops_split));
99 BM_face_splits_check_optimal(f, loops_split, STACK_SIZE(loops_split));
102 for (i = 0; i < STACK_SIZE(loops_split); i++) {
104 if (loops_split[i][0] == NULL) {
108 v_pair = STACK_PUSH_RET(verts_pair);
109 v_pair[0] = loops_split[i][0]->v;
110 v_pair[1] = loops_split[i][1]->v;
113 /* Clear and re-use to store duplicate faces, to remove after splitting is finished. */
114 STACK_CLEAR(loops_split);
116 for (i = 0; i < STACK_SIZE(verts_pair); i++) {
121 /* Note that duplicate edges in this case is very unlikely but it can happen, see T70287. */
122 bool edge_exists = (BM_edge_exists(verts_pair[i][0], verts_pair[i][1]) != NULL);
123 if ((l_pair[0] = BM_face_vert_share_loop(f, verts_pair[i][0])) &&
124 (l_pair[1] = BM_face_vert_share_loop(f, verts_pair[i][1]))) {
125 f_new = BM_face_split(bm, f, l_pair[0], l_pair[1], &l_new, NULL, edge_exists);
127 /* Check if duplicate faces have been created, store the loops for removal in this case.
128 * Note that this matches how triangulate works (newly created duplicates get removed). */
129 if (UNLIKELY(edge_exists)) {
130 BMLoop **l_pair_deferred_remove = NULL;
131 for (int j = 0; j < 2; j++) {
132 if (BM_face_find_double(l_pair[j]->f)) {
133 if (l_pair_deferred_remove == NULL) {
134 l_pair_deferred_remove = STACK_PUSH_RET(loops_split);
135 l_pair_deferred_remove[0] = NULL;
136 l_pair_deferred_remove[1] = NULL;
138 l_pair_deferred_remove[j] = l_pair[j];
148 if (!l_new || !f_new) {
154 // BMO_face_flag_enable(bm, f_new, FACE_NEW);
155 BMO_edge_flag_enable(bm, l_new->e, EDGE_OUT);
158 for (i = 0; i < STACK_SIZE(loops_split); i++) {
159 for (int j = 0; j < 2; j++) {
160 if (loops_split[i][j] != NULL) {
161 BM_face_kill(bm, loops_split[i][j]->f);
169 void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
174 const bool check_degenerate = BMO_slot_bool_get(op->slots_in, "check_degenerate");
175 BLI_LINKSTACK_DECLARE(faces, BMFace *);
177 BLI_LINKSTACK_INIT(faces);
179 /* tag so we won't touch ever (typically hidden faces) */
180 BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces_exclude", BM_FACE, FACE_EXCLUDE);
182 /* add all faces connected to verts */
183 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
187 BMO_vert_flag_enable(bm, v, VERT_INPUT);
188 BM_ITER_ELEM (l_iter, &iter, v, BM_LOOPS_OF_VERT) {
190 if (!BMO_face_flag_test(bm, f, FACE_EXCLUDE)) {
191 if (!BMO_face_flag_test(bm, f, FACE_TAG)) {
192 BMO_face_flag_enable(bm, f, FACE_TAG);
194 BLI_LINKSTACK_PUSH(faces, f);
199 /* flag edges even if these are not newly created
200 * this way cut-pairs that include co-linear edges will get
201 * predictable output. */
202 if (BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT)) {
203 BMO_edge_flag_enable(bm, l_iter->prev->e, EDGE_OUT_ADJ);
205 if (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT)) {
206 BMO_edge_flag_enable(bm, l_iter->e, EDGE_OUT_ADJ);
212 while ((f = BLI_LINKSTACK_POP(faces))) {
213 if (bm_face_connect_verts(bm, f, check_degenerate) == -1) {
214 BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
218 BLI_LINKSTACK_FREE(faces);
220 BMO_slot_buffer_from_enabled_flag(
221 bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT | EDGE_OUT_ADJ);