Blender V5.3
bmo_connect.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <array>
12
13#include "BLI_array.hh"
14#include "BLI_linklist_stack.hh"
15#include "BLI_utildefines.hh"
17
18#include "bmesh.hh"
19
20#include "intern/bmesh_operators_private.hh" /* own include */
21
22namespace blender {
23
24#define VERT_INPUT 1
25
26#define EDGE_OUT 1
27/* Edge spans 2 VERT_INPUT's, its a NOP,
28 * but include in "edges.out" */
29#define EDGE_OUT_ADJ 2
30
31#define FACE_TAG 2
32#define FACE_EXCLUDE 4
33
34static int bm_face_connect_verts(BMesh *bm, BMFace *f, const bool check_degenerate)
35{
36 const uint pair_split_max = f->len / 2;
37 Array<std::array<BMLoop *, 2>, BM_DEFAULT_NGON_STACK_SIZE> loops_split_buf(pair_split_max);
38 BMLoop *(*loops_split)[2] = reinterpret_cast<BMLoop *(*)[2]>(loops_split_buf.data());
39 STACK_DECLARE(loops_split);
40 Array<std::array<BMVert *, 2>, BM_DEFAULT_NGON_STACK_SIZE> verts_pair_buf(pair_split_max);
41 std::array<BMVert *, 2> *verts_pair = verts_pair_buf.data();
42 STACK_DECLARE(verts_pair);
43
44 BMLoop *l_tag_prev = nullptr, *l_tag_first = nullptr;
45 BMLoop *l_iter, *l_first;
46 uint i;
47 int result = 1;
48
49 STACK_INIT(loops_split, pair_split_max);
50 STACK_INIT(verts_pair, pair_split_max);
51
52 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
53 do {
54 if (BMO_vert_flag_test(bm, l_iter->v, VERT_INPUT) &&
55 /* Ensure this vertex isn't part of a contiguous group. */
56 ((BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT) == 0) ||
57 (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT) == 0)))
58 {
59 if (!l_tag_prev) {
60 l_tag_prev = l_tag_first = l_iter;
61 continue;
62 }
63
64 if (!BM_loop_is_adjacent(l_tag_prev, l_iter)) {
65 BMEdge *e;
66 e = BM_edge_exists(l_tag_prev->v, l_iter->v);
67 if (e == nullptr || !BMO_edge_flag_test(bm, e, EDGE_OUT)) {
68 BMLoop **l_pair = STACK_PUSH_RET(loops_split);
69 l_pair[0] = l_tag_prev;
70 l_pair[1] = l_iter;
71 }
72 }
73
74 l_tag_prev = l_iter;
75 }
76 } while ((l_iter = l_iter->next) != l_first);
77
78 if (STACK_SIZE(loops_split) == 0) {
79 return 0;
80 }
81
82 if (!BM_loop_is_adjacent(l_tag_first, l_tag_prev) &&
83 /* ensure we don't add the same pair twice */
84 (((loops_split[0][0] == l_tag_first) && (loops_split[0][1] == l_tag_prev)) == 0))
85 {
86 BMLoop **l_pair = STACK_PUSH_RET(loops_split);
87 l_pair[0] = l_tag_first;
88 l_pair[1] = l_tag_prev;
89 }
90
91 if (check_degenerate) {
92 BM_face_splits_check_legal(bm, f, loops_split, STACK_SIZE(loops_split));
93 }
94 else {
95 BM_face_splits_check_optimal(f, loops_split, STACK_SIZE(loops_split));
96 }
97
98 for (i = 0; i < STACK_SIZE(loops_split); i++) {
99 if (loops_split[i][0] == nullptr) {
100 continue;
101 }
102
103 std::array<BMVert *, 2> &v_pair = STACK_PUSH_RET(verts_pair);
104 v_pair[0] = loops_split[i][0]->v;
105 v_pair[1] = loops_split[i][1]->v;
106 }
107
108 /* Clear and re-use to store duplicate faces, to remove after splitting is finished. */
109 STACK_CLEAR(loops_split);
110
111 for (i = 0; i < STACK_SIZE(verts_pair); i++) {
112 BMFace *f_new;
113 BMLoop *l_new;
114 BMLoop *l_pair[2];
115
116 /* Note that duplicate edges in this case is very unlikely but it can happen, see #70287. */
117 bool edge_exists = (BM_edge_exists(verts_pair[i][0], verts_pair[i][1]) != nullptr);
118 if ((l_pair[0] = BM_face_vert_share_loop(f, verts_pair[i][0])) &&
119 (l_pair[1] = BM_face_vert_share_loop(f, verts_pair[i][1])))
120 {
121 f_new = BM_face_split(bm, f, l_pair[0], l_pair[1], &l_new, nullptr, edge_exists);
122
123 /* Check if duplicate faces have been created, store the loops for removal in this case.
124 * Note that this matches how triangulate works (newly created duplicates get removed). */
125 if (edge_exists) [[unlikely]] {
126 BMLoop **l_pair_deferred_remove = nullptr;
127 for (int j = 0; j < 2; j++) {
128 if (BM_face_find_double(l_pair[j]->f)) {
129 if (l_pair_deferred_remove == nullptr) {
130 l_pair_deferred_remove = STACK_PUSH_RET(loops_split);
131 l_pair_deferred_remove[0] = nullptr;
132 l_pair_deferred_remove[1] = nullptr;
133 }
134 l_pair_deferred_remove[j] = l_pair[j];
135 }
136 }
137 }
138 }
139 else {
140 f_new = nullptr;
141 l_new = nullptr;
142 }
143
144 if (!l_new || !f_new) {
145 result = -1;
146 break;
147 }
148
149 f = f_new;
150 // BMO_face_flag_enable(bm, f_new, FACE_NEW);
152 }
153
154 for (i = 0; i < STACK_SIZE(loops_split); i++) {
155 for (int j = 0; j < 2; j++) {
156 if (loops_split[i][j] != nullptr) {
157 BM_face_kill(bm, loops_split[i][j]->f);
158 }
159 }
160 }
161
162 return result;
163}
164
166{
167 BMOIter siter;
168 BMVert *v;
169 BMFace *f;
170 const bool check_degenerate = BMO_slot_bool_get(op->slots_in, "check_degenerate");
172
173 BLI_LINKSTACK_INIT(faces);
174
175 /* tag so we won't touch ever (typically hidden faces) */
177
178 /* add all faces connected to verts */
179 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
180 BMIter iter;
181 BMLoop *l_iter;
182
184 BM_ITER_ELEM (l_iter, &iter, v, BM_LOOPS_OF_VERT) {
185 f = l_iter->f;
187 if (!BMO_face_flag_test(bm, f, FACE_TAG)) {
189 if (f->len > 3) {
190 BLI_LINKSTACK_PUSH(faces, f);
191 }
192 }
193 }
194
195 /* flag edges even if these are not newly created
196 * this way cut-pairs that include co-linear edges will get
197 * predictable output. */
198 if (BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT)) {
200 }
201 if (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT)) {
203 }
204 }
205 }
206
207 /* connect faces */
208 while ((f = BLI_LINKSTACK_POP(faces))) {
209 if (bm_face_connect_verts(bm, f, check_degenerate) == -1) {
210 BMO_error_raise(bm, op, BMO_ERROR_FATAL, "Could not connect vertices");
211 }
212 }
213
214 BLI_LINKSTACK_FREE(faces);
215
217 bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT | EDGE_OUT_ADJ);
218}
219
220} // namespace blender
#define STACK_CLEAR(stack)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
#define STACK_PUSH_RET(stack)
#define BM_DEFAULT_NGON_STACK_SIZE
#define BM_FACE_FIRST_LOOP(p)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BMO_edge_flag_test(bm, e, oflag)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_vert_flag_test(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
#define EDGE_OUT
Definition bmo_bridge.cc:29
#define FACE_EXCLUDE
#define FACE_TAG
#define EDGE_OUT_ADJ
#define VERT_INPUT
const T * data() const
Definition BLI_array.hh:323
BMesh Iterators.
BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
unsigned int uint
Definition BKE_text.h:55
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
ATTR_WARN_UNUSED_RESULT const BMVert * v
void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
void BM_face_splits_check_optimal(BMFace *f, BMLoop *(*loops)[2], int len)
void BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void BM_face_kill(BMesh *bm, BMFace *f)
BMFace * BM_face_split(BMesh *bm, BMFace *f, BMLoop *l_a, BMLoop *l_b, BMLoop **r_l, BMEdge *example, const bool no_double)
Face Split.
BMLoop * BM_face_vert_share_loop(BMFace *f, BMVert *v)
Return the Loop Shared by Face and Vertex.
BMFace * BM_face_find_double(BMFace *f)
void BMO_error_raise(BMesh *bm, BMOperator *owner, eBMOpErrorLevel level, const char *msg) ATTR_NONNULL(1
static int bm_face_connect_verts(BMesh *bm, BMFace *f, const bool check_degenerate)
@ BMO_ERROR_FATAL
void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMFace * f
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]