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