Blender V5.3
bmesh_edgenet.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 <climits>
12
13#include "MEM_guardedalloc.h"
14
15#include "BLI_array.hh"
16#include "BLI_linklist.hh"
17#include "BLI_mempool.hh"
18#include "BLI_utildefines.hh"
19
20#include "bmesh.hh"
21#include "bmesh_edgenet.hh" /* own include */
22
23#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
24
25namespace blender {
26
27/* Struct for storing a path of verts walked over */
29 BMVert *prev; /* previous vertex */
30 int pass; /* path scanning pass value, for internal calculation */
31 int face; /* face index connected to the edge between this and the previous vert */
32 int flag; /* flag */
33};
34
35enum {
37};
38
43{
44 return BM_elem_flag_test(e, BM_ELEM_TAG) && ELEM(e->l, nullptr, e->l->radial_next);
45}
46
47static int bm_edge_face(BMEdge *e)
48{
49 return e->l ? BM_elem_index_get(e->l->f) : -1;
50}
51
56 LinkNode **edge_queue,
57 BLI_mempool *edge_queue_pool)
58{
59 BMEdge *e;
60 BMIter iter;
61
62 while (*edge_queue) {
63 e = static_cast<BMEdge *>(BLI_linklist_pop_pool(edge_queue, edge_queue_pool));
64 if (bm_edge_step_ok(e)) {
65 return e;
66 }
67 }
68
70 if (bm_edge_step_ok(e)) {
71 return e;
72 }
73 }
74
75 return nullptr;
76}
77
85 LinkNode **v_ls,
86 VertNetInfo *vnet_info,
87 BLI_mempool *path_pool)
88{
89 VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)];
90 const int pass = vn->pass;
91 uint v_ls_tot = 0;
92
93 do {
94 BLI_linklist_prepend_pool(v_ls, v, path_pool);
95 v_ls_tot += 1;
96 v = vn->prev;
97 vn = &vnet_info[BM_elem_index_get(v)];
98 } while (vn->pass == pass);
99
100 return v_ls_tot;
101}
102
108{
109 /* vert order doesn't matter */
110 uint v_ls_tot = 0;
111 LinkNode *v_ls = nullptr;
112 BMVert *v_pair[2] = {v1, v2};
113 uint i;
114
115 for (i = 0; i < 2; i++) {
116 BMVert *v = v_pair[i];
117 VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)];
118 const int pass = vn->pass;
119 do {
121 v_ls_tot += 1;
122 v = vn->prev;
123 vn = &vnet_info[BM_elem_index_get(v)];
124 } while (vn->pass == pass);
125 }
126
127 if (v_ls_tot) {
129 LinkNode *v_lnk;
130 for (i = 0, v_lnk = v_ls; i < v_ls_tot; v_lnk = v_lnk->next, i++) {
131 vert_arr[i] = static_cast<BMVert *>(v_lnk->link);
132 }
133
134 return BM_face_exists_overlap_subset(vert_arr.data(), int(v_ls_tot));
135 }
136 return false;
137}
138
142static BMFace *bm_edgenet_face_from_path(BMesh *bm, LinkNode *path, const uint path_len)
143{
144 BMFace *f;
145 LinkNode *v_lnk;
146 int i;
147 bool ok;
148
151
152 for (v_lnk = path, i = 0; v_lnk; v_lnk = v_lnk->next, i++) {
153 vert_arr[i] = static_cast<BMVert *>(v_lnk->link);
154 }
155
156 ok = BM_edges_from_verts(edge_arr.data(), vert_arr.data(), i);
157 BLI_assert(ok);
159
160/* no need for this, we do overlap checks before allowing the path to be used */
161#if 0
162 if (BM_face_exists_multi(vert_arr.data(), edge_arr.data(), path_len)) {
163 return nullptr;
164 }
165#endif
166
167 f = BM_face_create(bm, vert_arr.data(), edge_arr.data(), int(path_len), nullptr, BM_CREATE_NOP);
168
169 return f;
170}
171
178 LinkNode **v_ls,
179 VertNetInfo *vnet_info,
180 BLI_mempool *path_pool)
181{
182 const VertNetInfo *vn_curr;
183
184 BMEdge *e;
185 BMIter iter;
186 uint tot;
187 uint v_ls_tot;
188
189begin:
190 tot = 0;
191 v_ls_tot = 0;
192 vn_curr = &vnet_info[BM_elem_index_get(v_curr)];
193
194 BM_ITER_ELEM (e, &iter, v_curr, BM_EDGES_OF_VERT) {
195 BMVert *v_next = BM_edge_other_vert(e, v_curr);
196 if (v_next != vn_curr->prev) {
197 if (bm_edge_step_ok(e)) {
198 VertNetInfo *vn_next = &vnet_info[BM_elem_index_get(v_next)];
199
200 /* check we're not looping back on ourselves */
201 if (vn_curr->pass != vn_next->pass) {
202
203 if (vn_curr->pass == -vn_next->pass) {
204 if ((vn_curr->flag & VNINFO_FLAG_IS_MIXFACE) ||
205 (vn_next->flag & VNINFO_FLAG_IS_MIXFACE))
206 {
207 /* found connecting edge */
208 if (bm_edgenet_path_check_overlap(v_curr, v_next, vnet_info) == false) {
209 return e;
210 }
211 }
212 }
213 else {
214 vn_next->face = bm_edge_face(e);
215 vn_next->pass = vn_curr->pass;
216 vn_next->prev = v_curr;
217
218 /* flush flag down the path */
219 vn_next->flag &= ~VNINFO_FLAG_IS_MIXFACE;
220 if ((vn_curr->flag & VNINFO_FLAG_IS_MIXFACE) || (vn_next->face == -1) ||
221 (vn_next->face != vn_curr->face))
222 {
223 vn_next->flag |= VNINFO_FLAG_IS_MIXFACE;
224 }
225
226 /* add to the list! */
227 BLI_linklist_prepend_pool(v_ls, v_next, path_pool);
228 v_ls_tot += 1;
229 }
230 }
231 }
232 tot += 1;
233 }
234 }
235
236 /* trick to walk along wire-edge paths */
237 if (v_ls_tot == 1 && tot == 1) {
238 v_curr = static_cast<BMVert *>(BLI_linklist_pop_pool(v_ls, path_pool));
239/* avoid recursion, can crash on very large nets */
240#if 0
241 bm_edgenet_path_step(v_curr, v_ls, vnet_info, path_pool);
242#else
243 goto begin;
244#endif
245 }
246
247 return nullptr;
248}
249
256 const int pass_nr,
257 const uint path_cost_max,
258 uint *r_path_len,
259 uint *r_path_cost,
260 VertNetInfo *vnet_info,
261 BLI_mempool *path_pool)
262{
263 VertNetInfo *vn_1, *vn_2;
264 const int f_index = bm_edge_face(e);
265 bool found;
266
267 LinkNode *v_ls_prev = nullptr;
268 LinkNode *v_ls_next = nullptr;
269
270 uint path_cost_accum = 0;
271
273
274 *r_path_len = 0;
275 *r_path_cost = 0;
276
277 vn_1 = &vnet_info[BM_elem_index_get(e->v1)];
278 vn_2 = &vnet_info[BM_elem_index_get(e->v2)];
279
280 vn_1->pass = pass_nr;
281 vn_2->pass = -pass_nr;
282
283 vn_1->prev = e->v2;
284 vn_2->prev = e->v1;
285
286 vn_1->face = vn_2->face = f_index;
287
288 vn_1->flag = vn_2->flag = (f_index == -1) ? VNINFO_FLAG_IS_MIXFACE : 0;
289
290 /* Prime the search-list. */
291 BLI_linklist_prepend_pool(&v_ls_prev, e->v1, path_pool);
292 BLI_linklist_prepend_pool(&v_ls_prev, e->v2, path_pool);
293
294 do {
295 found = false;
296
297 /* no point to continue, we're over budget */
298 if (path_cost_accum >= path_cost_max) {
299 BLI_linklist_free_pool(v_ls_next, nullptr, path_pool);
300 BLI_linklist_free_pool(v_ls_prev, nullptr, path_pool);
301 return nullptr;
302 }
303
304 while (v_ls_prev) {
305 const LinkNode *v_ls_next_old = v_ls_next;
306 BMVert *v = static_cast<BMVert *>(BLI_linklist_pop_pool(&v_ls_prev, path_pool));
307 BMEdge *e_found = bm_edgenet_path_step(v, &v_ls_next, vnet_info, path_pool);
308
309 if (e_found) {
310 LinkNode *path = nullptr;
311 uint path_len;
312 BLI_linklist_free_pool(v_ls_next, nullptr, path_pool);
313 BLI_linklist_free_pool(v_ls_prev, nullptr, path_pool);
314
315 // BLI_assert(BLI_mempool_len(path_pool) == 0);
316
317 path_len = bm_edgenet_path_from_pass(e_found->v1, &path, vnet_info, path_pool);
319 path_len += bm_edgenet_path_from_pass(e_found->v2, &path, vnet_info, path_pool);
320 *r_path_len = path_len;
321 *r_path_cost = path_cost_accum;
322 return path;
323 }
324
325 /* check if a change was made */
326 if (v_ls_next_old != v_ls_next) {
327 found = true;
328 }
329 }
330 BLI_assert(v_ls_prev == nullptr);
331
332 path_cost_accum++;
333
334 /* swap */
335 v_ls_prev = v_ls_next;
336 v_ls_next = nullptr;
337
338 } while (found);
339
340 BLI_assert(v_ls_prev == nullptr);
341 BLI_assert(v_ls_next == nullptr);
342
343 /* tag not to search again */
345
346 return nullptr;
347}
348
354 int *pass_nr,
355 uint path_cost_max,
356 uint *r_path_len,
357 uint *r_path_cost,
358 VertNetInfo *vnet_info,
359 BLI_mempool *path_pool)
360{
361 LinkNode *path;
362 uint path_cost;
363
365 e, *pass_nr, path_cost_max, r_path_len, &path_cost, vnet_info, path_pool);
366 (*pass_nr)++;
367
368 if (path == nullptr) {
369 return nullptr;
370 }
371 if (path_cost < 1) {
372 /* any face that takes 1 iteration to find we consider valid */
373 return path;
374 }
375
376 /* Check every edge to see if any can give a better path.
377 * This avoids very strange/long paths from being created. */
378
379 const uint path_len = *r_path_len;
380 uint i, i_prev;
382 LinkNode *v_lnk;
383
384 for (v_lnk = path, i = 0; v_lnk; v_lnk = v_lnk->next, i++) {
385 vert_arr[i] = static_cast<BMVert *>(v_lnk->link);
386 }
387
388 i_prev = path_len - 1;
389 for (i = 0; i < path_len; i++) {
390 BMEdge *e_other = BM_edge_exists(vert_arr[i], vert_arr[i_prev]);
391 if (e_other != e) {
392 LinkNode *path_test;
393 uint path_len_test;
394 uint path_cost_test;
395
396 path_test = bm_edgenet_path_calc(
397 e_other, *pass_nr, path_cost, &path_len_test, &path_cost_test, vnet_info, path_pool);
398 (*pass_nr)++;
399
400 if (path_test) {
401 BLI_assert(path_cost_test < path_cost);
402
403 BLI_linklist_free_pool(path, nullptr, path_pool);
404 path = path_test;
405 *r_path_len = path_len_test;
406 *r_path_cost = path_cost_test;
407 path_cost = path_cost_test;
408 }
409 }
410
411 i_prev = i;
412 }
413
414 return path;
415}
416
417void BM_mesh_edgenet(BMesh *bm, const bool use_edge_tag, const bool use_new_face_tag)
418{
419 VertNetInfo *vnet_info = MEM_new_array_zeroed<VertNetInfo>(size_t(bm->totvert), __func__);
420 BLI_mempool *edge_queue_pool = BLI_mempool_create(sizeof(LinkNode), 0, 512, BLI_MEMPOOL_NOP);
421 BLI_mempool *path_pool = BLI_mempool_create(sizeof(LinkNode), 0, 512, BLI_MEMPOOL_NOP);
422 LinkNode *edge_queue = nullptr;
423
424 BMEdge *e;
425 BMIter iter;
426
427 int pass_nr = 1;
428
429 if (use_edge_tag == false) {
430 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
432 }
433 }
434
436
437 while (true) {
438 LinkNode *path = nullptr;
439 uint path_len;
440 uint path_cost;
441
442 e = bm_edgenet_edge_get_next(bm, &edge_queue, edge_queue_pool);
443 if (e == nullptr) {
444 break;
445 }
446
447 BLI_assert(bm_edge_step_ok(e) == true);
448
450 e, &pass_nr, UINT_MAX, &path_len, &path_cost, vnet_info, path_pool);
451
452 if (path) {
453 BMFace *f = bm_edgenet_face_from_path(bm, path, path_len);
454 /* queue edges to operate on */
455 BMLoop *l_first, *l_iter;
456 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
457 do {
458 if (bm_edge_step_ok(l_iter->e)) {
459 BLI_linklist_prepend_pool(&edge_queue, l_iter->e, edge_queue_pool);
460 }
461 } while ((l_iter = l_iter->next) != l_first);
462
463 if (use_new_face_tag) {
465 }
466
467 /* the face index only needs to be unique, not kept valid */
468 BM_elem_index_set(f, bm->totface - 1); /* set_dirty */
469 }
470
471 BLI_linklist_free_pool(path, nullptr, path_pool);
472 BLI_assert(BLI_mempool_len(path_pool) == 0);
473 }
474
476
477 BLI_mempool_destroy(edge_queue_pool);
478 BLI_mempool_destroy(path_pool);
479 MEM_delete(vnet_info);
480}
481
482} // namespace blender
Read Blender memory allocation and freeing.
#define UNUSED_VARS_NDEBUG(...)
#define ELEM(...)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
const T * data() const
Definition BLI_array.hh:323
#define UINT_MAX
Definition hash_md5.cc:46
BMesh Iterators.
void void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
unsigned int uint
Definition BKE_text.h:55
ATTR_WARN_UNUSED_RESULT const BMVert * v
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
static LinkNode * bm_edgenet_path_calc_best(BMEdge *e, int *pass_nr, uint path_cost_max, uint *r_path_len, uint *r_path_cost, VertNetInfo *vnet_info, BLI_mempool *path_pool)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static BMEdge * bm_edgenet_edge_get_next(BMesh *bm, LinkNode **edge_queue, BLI_mempool *edge_queue_pool)
void BM_mesh_edgenet(BMesh *bm, const bool use_edge_tag, const bool use_new_face_tag)
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
static int bm_edge_face(BMEdge *e)
static BMEdge * bm_edgenet_path_step(BMVert *v_curr, LinkNode **v_ls, VertNetInfo *vnet_info, BLI_mempool *path_pool)
static BMFace * bm_edgenet_face_from_path(BMesh *bm, LinkNode *path, const uint path_len)
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
bool BM_edges_from_verts(BMEdge **edge_arr, BMVert **vert_arr, const int len)
void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool)
static bool bm_edge_step_ok(BMEdge *e)
void * BLI_linklist_pop_pool(LinkNode **listp, struct BLI_mempool *mempool) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
iter begin(iter)
void BLI_linklist_reverse(LinkNode **listp) ATTR_NONNULL(1)
@ BLI_MEMPOOL_NOP
@ VNINFO_FLAG_IS_MIXFACE
static bool bm_edgenet_path_check_overlap(BMVert *v1, BMVert *v2, VertNetInfo *vnet_info)
int BLI_mempool_len(const BLI_mempool *pool) ATTR_NONNULL(1)
static LinkNode * bm_edgenet_path_calc(BMEdge *e, const int pass_nr, const uint path_cost_max, uint *r_path_len, uint *r_path_cost, VertNetInfo *vnet_info, BLI_mempool *path_pool)
static uint bm_edgenet_path_from_pass(BMVert *v, LinkNode **v_ls, VertNetInfo *vnet_info, BLI_mempool *path_pool)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
struct BMLoop * next
struct BMEdge * e
struct LinkNode * next