Blender V5.3
bmesh_region_match.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
21
22#include <algorithm>
23#include <cstring>
24
25#include "BLI_array.hh"
26#include "BLI_ghash.hh"
27#include "BLI_linklist.hh"
28#include "BLI_linklist_stack.hh"
29#include "BLI_listbase.hh"
30#include "BLI_mempool.hh"
31
32#include "MEM_guardedalloc.h"
33
34#include "bmesh.hh"
35
36#include "tools/bmesh_region_match.hh" /* own include */
37
38/* avoid re-creating ghash and pools for each search */
39#define USE_WALKER_REUSE
40
41/* do a first-pass id of all vertices,
42 * this avoids expensive checks on every item later on
43 * (works fine without, just slower) */
44#define USE_PIVOT_FASTMATCH
45
46/* otherwise use active element as pivot, for quick tests only */
47#define USE_PIVOT_SEARCH
48
49// #define DEBUG_TIME
50// #define DEBUG_PRINT
51
52#ifdef DEBUG_TIME
53# include "BLI_time.hh"
55#endif
56
57#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
58
59namespace blender {
60
61/* -------------------------------------------------------------------- */
64
65#define PRIME_VERT_INIT 100003
66
68
70 template<typename BMElemT> uint64_t operator()(const BMElemT *ele) const
71 {
72 return uint64_t(BM_elem_index_get(ele));
73 }
74};
75
77 template<typename BMElemT> bool operator()(const BMElemT *a, const BMElemT *b) const
78 {
80 return a == b;
81 }
82};
83
85
86struct UIDFaceStep;
87struct UIDFaceStepItem;
88
89struct UIDWalk {
90
91 /* List of faces we can step onto (UIDFaceStep's) */
92 ListBaseT<UIDFaceStep> faces_step;
93
94 /* Face & Vert UID's */
97
98 /* memory pool for LinkNode's */
100
101 /* memory pool for LinkBase's */
103
104 /* memory pool for UIDFaceStep's */
107
108 /* Optionally use face-tag to isolate search */
110
111 /* Increment for each pass added */
113
114 /* runtime vars, avoid re-creating each pass */
115 struct {
116 GHash *verts_uid; /* BMVert -> UID */
118
119 GHash *faces_from_uid; /* UID -> UIDFaceStepItem */
120
124};
125
126/* stores a set of potential faces to step onto */
129
130 /* unsorted 'BMFace' */
132
133 /* faces sorted into 'UIDFaceStepItem' */
134 ListBaseT<UIDFaceStepItem> items;
135};
136
137/* store face-lists with same HID. */
145
147{
148 if (uidwalk->use_face_isolate) {
150 }
151 return true;
152}
153
155{
156 void **ret;
157 ret = BLI_ghash_lookup_p(uidwalk->verts_uid, v);
158 if (ret) {
159 *r_uid = reinterpret_cast<UID_Int>(*ret);
160 return true;
161 }
162 return false;
163}
164
166{
167 void **ret;
168 ret = BLI_ghash_lookup_p(uidwalk->faces_uid, f);
169 if (ret) {
170 *r_uid = reinterpret_cast<UID_Int>(*ret);
171 return true;
172 }
173 return false;
174}
175
176static uint ghashutil_bmelem_indexhash(const void *key)
177{
178 return uint(BMElemIndexHash{}(static_cast<const BMElem *>(key)));
179}
180
181static bool ghashutil_bmelem_indexcmp(const void *a, const void *b)
182{
183 return !BMElemIndexEq{}(static_cast<const BMElem *>(a), static_cast<const BMElem *>(b));
184}
185
186static GHash *ghash_bmelem_new_ex(const char *info, const uint nentries_reserve)
187{
188 return BLI_ghash_new_ex(
190}
191
192static GHash *ghash_bmelem_new(const char *info)
193{
194 return ghash_bmelem_new_ex(info, 0);
195}
196
197static void bm_uidwalk_init(UIDWalk *uidwalk,
198 const uint faces_src_region_len,
199 const uint verts_src_region_len)
200{
201 uidwalk->faces_step.clear_no_delete();
202
203 uidwalk->verts_uid = ghash_bmelem_new_ex(__func__, verts_src_region_len);
204 uidwalk->faces_uid = ghash_bmelem_new_ex(__func__, faces_src_region_len);
205
206 uidwalk->cache.verts_uid = ghash_bmelem_new(__func__);
207 uidwalk->cache.faces_step = MEM_new<BMFaceIndexSet>(__func__);
208
209 /* works because 'int' ghash works for intptr_t too */
210 uidwalk->cache.faces_from_uid = BLI_ghash_int_new(__func__);
211
212 uidwalk->cache.rehash_store = nullptr;
213 uidwalk->cache.rehash_store_len = 0;
214
215 uidwalk->use_face_isolate = false;
216
217 /* smaller pool's for faster clearing */
218 uidwalk->link_pool = BLI_mempool_create(sizeof(LinkNode), 64, 64, BLI_MEMPOOL_NOP);
219 uidwalk->step_pool = BLI_mempool_create(sizeof(UIDFaceStep), 64, 64, BLI_MEMPOOL_NOP);
221
222 uidwalk->pass = 1;
223}
224
225static void bm_uidwalk_clear(UIDWalk *uidwalk)
226{
227 uidwalk->faces_step.clear_no_delete();
228
229 BLI_ghash_clear(uidwalk->verts_uid, nullptr, nullptr);
230 BLI_ghash_clear(uidwalk->faces_uid, nullptr, nullptr);
231
232 BLI_ghash_clear(uidwalk->cache.verts_uid, nullptr, nullptr);
233 uidwalk->cache.faces_step->clear();
234 BLI_ghash_clear(uidwalk->cache.faces_from_uid, nullptr, nullptr);
235
236 /* keep rehash_store as-is, for reuse */
237
238 uidwalk->use_face_isolate = false;
239
243
244 uidwalk->pass = 1;
245}
246
247static void bm_uidwalk_free(UIDWalk *uidwalk)
248{
254
255 BLI_ghash_free(uidwalk->verts_uid, nullptr, nullptr);
256 BLI_ghash_free(uidwalk->faces_uid, nullptr, nullptr);
257
258 /* cache */
259 BLI_ghash_free(uidwalk->cache.verts_uid, nullptr, nullptr);
260 MEM_delete(uidwalk->cache.faces_step);
261 BLI_ghash_free(uidwalk->cache.faces_from_uid, nullptr, nullptr);
262 MEM_SAFE_DELETE(uidwalk->cache.rehash_store);
263
267}
268
270{
271#define PRIME_VERT_SMALL 7
272#define PRIME_VERT_MID 43
273#define PRIME_VERT_LARGE 1031
274
275#define PRIME_FACE_SMALL 13
276#define PRIME_FACE_MID 53
277
278 UID_Int uid;
279
280 uid = uidwalk->pass * PRIME_VERT_LARGE;
281
282 /* vert -> other */
283 {
284 uint tot = 0;
285 BMIter eiter;
286 BMEdge *e;
287 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
288 BMVert *v_other = BM_edge_other_vert(e, v);
289 UID_Int uid_other;
290 if (bm_uidwalk_vert_lookup(uidwalk, v_other, &uid_other)) {
291 uid ^= (uid_other * PRIME_VERT_SMALL);
292 tot += 1;
293 }
294 }
295 uid ^= (tot * PRIME_VERT_MID);
296 }
297
298 /* faces */
299 {
300 uint tot = 0;
301 BMIter iter;
302 BMFace *f;
303
304 BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
305 UID_Int uid_other;
306 if (bm_uidwalk_face_lookup(uidwalk, f, &uid_other)) {
307 uid ^= (uid_other * PRIME_FACE_SMALL);
308 tot += 1;
309 }
310 }
311 uid ^= (tot * PRIME_FACE_MID);
312 }
313
314 return uid;
315
316#undef PRIME_VERT_SMALL
317#undef PRIME_VERT_MID
318#undef PRIME_VERT_LARGE
319
320#undef PRIME_FACE_SMALL
321#undef PRIME_FACE_MID
322}
323
325{
326#define PRIME_VERT_SMALL 11
327
328#define PRIME_FACE_SMALL 17
329#define PRIME_FACE_LARGE 1013
330
331 UID_Int uid;
332
333 uid = uidwalk->pass * uint(f->len) * PRIME_FACE_LARGE;
334
335 /* face-verts */
336 {
337 BMLoop *l_iter, *l_first;
338
339 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
340 do {
341 UID_Int uid_other;
342 if (bm_uidwalk_vert_lookup(uidwalk, l_iter->v, &uid_other)) {
343 uid ^= (uid_other * PRIME_VERT_SMALL);
344 }
345 } while ((l_iter = l_iter->next) != l_first);
346 }
347
348 /* face-faces (connected by edge) */
349 {
350 BMLoop *l_iter, *l_first;
351
352 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
353 do {
354 if (l_iter->radial_next != l_iter) {
355 BMLoop *l_iter_radial = l_iter->radial_next;
356 do {
357 UID_Int uid_other;
358 if (bm_uidwalk_face_lookup(uidwalk, l_iter_radial->f, &uid_other)) {
359 uid ^= (uid_other * PRIME_FACE_SMALL);
360 }
361 } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter);
362 }
363 } while ((l_iter = l_iter->next) != l_first);
364 }
365
366 return uid;
367
368#undef PRIME_VERT_SMALL
369
370#undef PRIME_FACE_SMALL
371#undef PRIME_FACE_LARGE
372}
373
374static void bm_uidwalk_rehash_reserve(UIDWalk *uidwalk, uint rehash_store_len_new)
375{
376 if (rehash_store_len_new > uidwalk->cache.rehash_store_len) [[unlikely]] {
377 /* Avoid re-allocations. */
378 rehash_store_len_new *= 2;
379 uidwalk->cache.rehash_store = static_cast<UID_Int *>(MEM_realloc_uninitialized(
380 uidwalk->cache.rehash_store, rehash_store_len_new * sizeof(*uidwalk->cache.rehash_store)));
381 uidwalk->cache.rehash_store_len = rehash_store_len_new;
382 }
383}
384
388static void bm_uidwalk_rehash(UIDWalk *uidwalk)
389{
390 GHashIterator gh_iter;
391 UID_Int *uid_store;
392 uint i;
393
394 uint rehash_store_len_new = std::max(BLI_ghash_len(uidwalk->verts_uid),
395 BLI_ghash_len(uidwalk->faces_uid));
396
397 bm_uidwalk_rehash_reserve(uidwalk, rehash_store_len_new);
398 uid_store = uidwalk->cache.rehash_store;
399
400 /* verts */
401 i = 0;
402 GHASH_ITER (gh_iter, uidwalk->verts_uid) {
403 BMVert *v = static_cast<BMVert *>(BLI_ghashIterator_getKey(&gh_iter));
404 uid_store[i++] = bm_uidwalk_calc_vert_uid(uidwalk, v);
405 }
406 i = 0;
407 GHASH_ITER (gh_iter, uidwalk->verts_uid) {
408 void **uid_p = BLI_ghashIterator_getValue_p(&gh_iter);
409 *(reinterpret_cast<UID_Int *>(uid_p)) = uid_store[i++];
410 }
411
412 /* faces */
413 i = 0;
414 GHASH_ITER (gh_iter, uidwalk->faces_uid) {
415 BMFace *f = static_cast<BMFace *>(BLI_ghashIterator_getKey(&gh_iter));
416 uid_store[i++] = bm_uidwalk_calc_face_uid(uidwalk, f);
417 }
418 i = 0;
419 GHASH_ITER (gh_iter, uidwalk->faces_uid) {
420 void **uid_p = BLI_ghashIterator_getValue_p(&gh_iter);
421 *(reinterpret_cast<UID_Int *>(uid_p)) = uid_store[i++];
422 }
423}
424
426 LinkNode *faces,
427 const uint faces_len,
428 const bool is_init)
429{
430 UID_Int *uid_store;
431 LinkNode *f_link;
432 uint i;
433
434 bm_uidwalk_rehash_reserve(uidwalk, faces_len);
435 uid_store = uidwalk->cache.rehash_store;
436
437 i = 0;
438 for (f_link = faces; f_link; f_link = f_link->next) {
439 BMFace *f = static_cast<BMFace *>(f_link->link);
440 uid_store[i++] = bm_uidwalk_calc_face_uid(uidwalk, f);
441 }
442
443 i = 0;
444 if (is_init) {
445 for (f_link = faces; f_link; f_link = f_link->next) {
446 BMFace *f = static_cast<BMFace *>(f_link->link);
447 BLI_ghash_insert(uidwalk->faces_uid, f, reinterpret_cast<void *>(uid_store[i++]));
448 }
449 }
450 else {
451 for (f_link = faces; f_link; f_link = f_link->next) {
452 BMFace *f = static_cast<BMFace *>(f_link->link);
453 void **uid_p = BLI_ghash_lookup_p(uidwalk->faces_uid, f);
454 *(reinterpret_cast<UID_Int *>(uid_p)) = uid_store[i++];
455 }
456 }
457}
458
459static bool bm_vert_is_uid_connect(UIDWalk *uidwalk, BMVert *v)
460{
461 BMIter eiter;
462 BMEdge *e;
463
464 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
465 BMVert *v_other = BM_edge_other_vert(e, v);
466 if (BLI_ghash_haskey(uidwalk->verts_uid, v_other)) {
467 return true;
468 }
469 }
470 return false;
471}
472
473static void bm_uidwalk_pass_add(UIDWalk *uidwalk, LinkNode *faces_pass, const uint faces_pass_len)
474{
475 GHashIterator gh_iter;
476 GHash *verts_uid_pass;
477 LinkNode *f_link;
478
479 UIDFaceStep *fstep;
480
481 BLI_assert(faces_pass_len == uint(BLI_linklist_count(faces_pass)));
482
483 /* rehash faces now all their verts have been added */
484 bm_uidwalk_rehash_facelinks(uidwalk, faces_pass, faces_pass_len, true);
485
486 /* create verts_new */
487 verts_uid_pass = uidwalk->cache.verts_uid;
488 BMFaceIndexSet *faces_step_next = uidwalk->cache.faces_step;
489
490 BLI_assert(BLI_ghash_len(verts_uid_pass) == 0);
491 BLI_assert(faces_step_next->is_empty());
492
493 /* Add the face_step data from connected faces, creating new passes */
494 fstep = static_cast<UIDFaceStep *>(BLI_mempool_alloc(uidwalk->step_pool));
495 BLI_addhead(&uidwalk->faces_step, fstep);
496 fstep->faces = nullptr;
497 fstep->items.clear_no_delete();
498
499 for (f_link = faces_pass; f_link; f_link = f_link->next) {
500 BMFace *f = static_cast<BMFace *>(f_link->link);
501 BMLoop *l_iter, *l_first;
502
503 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
504 do {
505 /* fill verts_new */
506 void **val_p;
507 if (!BLI_ghash_haskey(uidwalk->verts_uid, l_iter->v) &&
508 !BLI_ghash_ensure_p(verts_uid_pass, l_iter->v, &val_p) &&
509 (bm_vert_is_uid_connect(uidwalk, l_iter->v) == true))
510 {
511 const UID_Int uid = bm_uidwalk_calc_vert_uid(uidwalk, l_iter->v);
512 *val_p = reinterpret_cast<void *>(uid);
513 }
514
515 /* fill faces_step_next */
516 if (l_iter->radial_next != l_iter) {
517 BMLoop *l_iter_radial = l_iter->radial_next;
518 do {
519 if (!BLI_ghash_haskey(uidwalk->faces_uid, l_iter_radial->f) &&
520 !faces_step_next->contains(l_iter_radial->f) &&
521 bm_uidwalk_face_test(uidwalk, l_iter_radial->f))
522 {
523 faces_step_next->add(l_iter_radial->f);
524
525 /* add to fstep */
526 BLI_linklist_prepend_pool(&fstep->faces, l_iter_radial->f, uidwalk->link_pool);
527 }
528 } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter);
529 }
530 } while ((l_iter = l_iter->next) != l_first);
531 }
532
533 /* faces_uid.update(verts_new) */
534 GHASH_ITER (gh_iter, verts_uid_pass) {
535 BMVert *v = static_cast<BMVert *>(BLI_ghashIterator_getKey(&gh_iter));
536 void *uid_p = BLI_ghashIterator_getValue(&gh_iter);
537 BLI_ghash_insert(uidwalk->verts_uid, v, uid_p);
538 }
539
540 /* rehash faces now all their verts have been added */
541 bm_uidwalk_rehash_facelinks(uidwalk, faces_pass, faces_pass_len, false);
542
543 uidwalk->pass += 1;
544
545 BLI_ghash_clear(uidwalk->cache.verts_uid, nullptr, nullptr);
546 uidwalk->cache.faces_step->clear();
547}
548
550{
551 BMLoop *l_iter = e->l;
552 uint f_arr_len = uint(BM_edge_face_count(e));
554 uint fstep_num = 0, i = 0;
555
556 do {
557 BMFace *f = l_iter->f;
558 if (bm_uidwalk_face_test(uidwalk, f)) {
559 f_arr[i++] = f;
560 }
561 } while ((l_iter = l_iter->radial_next) != e->l);
562 BLI_assert(i <= f_arr_len);
563 f_arr_len = i;
564
565 std::sort(f_arr.begin(), f_arr.begin() + f_arr_len, [](BMFace *f1, BMFace *f2) {
566 return f1->len < f2->len;
567 });
568
569 /* start us off! */
570 {
571 const UID_Int uid = PRIME_VERT_INIT;
572 BLI_ghash_insert(uidwalk->verts_uid, e->v1, reinterpret_cast<void *>(uid));
573 BLI_ghash_insert(uidwalk->verts_uid, e->v2, reinterpret_cast<void *>(uid));
574 }
575
576 /* turning an array into LinkNode's seems odd,
577 * but this is just for initialization,
578 * elsewhere using LinkNode's makes more sense */
579 for (i = 0; i < f_arr_len;) {
580 LinkNode *faces_pass = nullptr;
581 const uint i_init = i;
582 const int f_len = f_arr[i]->len;
583
584 do {
585 BLI_linklist_prepend_pool(&faces_pass, f_arr[i++], uidwalk->link_pool);
586 } while (i < f_arr_len && (f_len == f_arr[i]->len));
587
588 bm_uidwalk_pass_add(uidwalk, faces_pass, i - i_init);
589 BLI_linklist_free_pool(faces_pass, nullptr, uidwalk->link_pool);
590 fstep_num += 1;
591 }
592
593 return fstep_num;
594}
595
596#undef PRIME_VERT_INIT
597
599
600/* -------------------------------------------------------------------- */
603
604static int facestep_sort(const void *a, const void *b)
605{
606 const UIDFaceStepItem *fstep_a = static_cast<const UIDFaceStepItem *>(a);
607 const UIDFaceStepItem *fstep_b = static_cast<const UIDFaceStepItem *>(b);
608 return (fstep_a->uid > fstep_b->uid) ? 1 : 0;
609}
610
615static bool bm_uidwalk_facestep_begin(UIDWalk *uidwalk, UIDFaceStep *fstep)
616{
617 LinkNode *f_link, *f_link_next, **f_link_prev_p;
618 bool ok = false;
619
620 BLI_assert(BLI_ghash_len(uidwalk->cache.faces_from_uid) == 0);
621 BLI_assert(fstep->items.is_empty());
622
623 f_link_prev_p = &fstep->faces;
624 for (f_link = fstep->faces; f_link; f_link = f_link_next) {
625 BMFace *f = static_cast<BMFace *>(f_link->link);
626 f_link_next = f_link->next;
627
628 /* possible another pass added this face already, free in that case */
629 if (!BLI_ghash_haskey(uidwalk->faces_uid, f)) {
630 const UID_Int uid = bm_uidwalk_calc_face_uid(uidwalk, f);
631 UIDFaceStepItem *fstep_item;
632 void **val_p;
633
634 ok = true;
635
636 if (BLI_ghash_ensure_p(uidwalk->cache.faces_from_uid, reinterpret_cast<void *>(uid), &val_p))
637 {
638 fstep_item = static_cast<UIDFaceStepItem *>(*val_p);
639 }
640 else {
641 fstep_item = static_cast<UIDFaceStepItem *>(*val_p = BLI_mempool_alloc(
642 uidwalk->step_pool_items));
643
644 /* add to start, so its handled on the next round of passes */
645 BLI_addhead(&fstep->items, fstep_item);
646 fstep_item->uid = uid;
647 fstep_item->list = nullptr;
648 fstep_item->list_len = 0;
649 }
650
651 BLI_linklist_prepend_pool(&fstep_item->list, f, uidwalk->link_pool);
652 fstep_item->list_len += 1;
653
654 f_link_prev_p = &f_link->next;
655 }
656 else {
657 *f_link_prev_p = f_link->next;
658 BLI_mempool_free(uidwalk->link_pool, f_link);
659 }
660 }
661
662 BLI_ghash_clear(uidwalk->cache.faces_from_uid, nullptr, nullptr);
663
665
666 return ok;
667}
668
672static void bm_uidwalk_facestep_end(UIDWalk *uidwalk, UIDFaceStep *fstep)
673{
674 while (UIDFaceStepItem *fstep_item = static_cast<UIDFaceStepItem *>(BLI_pophead(&fstep->items)))
675 {
676 BLI_mempool_free(uidwalk->step_pool_items, fstep_item);
677 }
678}
679
680static void bm_uidwalk_facestep_free(UIDWalk *uidwalk, UIDFaceStep *fstep)
681{
682 LinkNode *f_link, *f_link_next;
683
684 BLI_assert(fstep->items.is_empty());
685
686 for (f_link = fstep->faces; f_link; f_link = f_link_next) {
687 f_link_next = f_link->next;
688 BLI_mempool_free(uidwalk->link_pool, f_link);
689 }
690
691 BLI_remlink(&uidwalk->faces_step, fstep);
692 BLI_mempool_free(uidwalk->step_pool, fstep);
693}
694
696
697/* -------------------------------------------------------------------- */
698/* Main Loop to match up regions */
699
705#ifdef USE_WALKER_REUSE
706 UIDWalk *w_src,
707 UIDWalk *w_dst,
708#endif
709 BMEdge *e_src,
710 BMEdge *e_dst,
711 const uint faces_src_region_len,
712 const uint verts_src_region_len,
713 uint *r_faces_result_len)
714{
715#ifndef USE_WALKER_REUSE
716 UIDWalk w_src_, w_dst_;
717 UIDWalk *w_src = &w_src_, *w_dst = &w_dst_;
718#endif
719 BMFace **faces_result = nullptr;
720 bool found = false;
721
722 BLI_assert(e_src != e_dst);
723
724#ifndef USE_WALKER_REUSE
725 bm_uidwalk_init(w_src, faces_src_region_len, verts_src_region_len);
726 bm_uidwalk_init(w_dst, faces_src_region_len, verts_src_region_len);
727#endif
728
729 w_src->use_face_isolate = true;
730
731 /* setup the initial state */
732 if (bm_uidwalk_init_from_edge(w_src, e_src) != bm_uidwalk_init_from_edge(w_dst, e_dst))
733 [[unlikely]]
734 {
735 /* should never happen, if verts passed are compatible, but to be safe... */
736 goto finally;
737 }
738
739 bm_uidwalk_rehash_reserve(w_src, std::max(faces_src_region_len, verts_src_region_len));
740 bm_uidwalk_rehash_reserve(w_dst, std::max(faces_src_region_len, verts_src_region_len));
741
742 while (true) {
743 bool ok = false;
744
745 UIDFaceStep *fstep_src = w_src->faces_step.first();
746 UIDFaceStep *fstep_dst = w_dst->faces_step.first();
747
748 BLI_assert(w_src->faces_step.count() == w_dst->faces_step.count());
749
750 while (fstep_src) {
751
752 /* even if the destination has faces,
753 * it's not important, since the source doesn't, free and move-on. */
754 if (fstep_src->faces == nullptr) {
755 UIDFaceStep *fstep_src_next = fstep_src->next;
756 UIDFaceStep *fstep_dst_next = fstep_dst->next;
757 bm_uidwalk_facestep_free(w_src, fstep_src);
758 bm_uidwalk_facestep_free(w_dst, fstep_dst);
759 fstep_src = fstep_src_next;
760 fstep_dst = fstep_dst_next;
761 continue;
762 }
763
764 if (bm_uidwalk_facestep_begin(w_src, fstep_src) &&
765 bm_uidwalk_facestep_begin(w_dst, fstep_dst))
766 {
767 /* Step over face-lists with matching UID's
768 * both lists are sorted, so no need for lookups.
769 * The data is created on 'begin' and cleared on 'end' */
770 UIDFaceStepItem *fstep_item_src;
771 UIDFaceStepItem *fstep_item_dst;
772 for (fstep_item_src = fstep_src->items.first(), fstep_item_dst = fstep_dst->items.first();
773 fstep_item_src && fstep_item_dst;
774 fstep_item_src = fstep_item_src->next, fstep_item_dst = fstep_item_dst->next)
775 {
776 while ((fstep_item_dst != nullptr) && (fstep_item_dst->uid < fstep_item_src->uid)) {
777 fstep_item_dst = fstep_item_dst->next;
778 }
779
780 if ((fstep_item_dst == nullptr) || (fstep_item_src->uid != fstep_item_dst->uid) ||
781 (fstep_item_src->list_len > fstep_item_dst->list_len))
782 {
783 /* if the target walker has less than the source
784 * then the islands don't match, bail early */
785 ok = false;
786 break;
787 }
788
789 if (fstep_item_src->list_len == fstep_item_dst->list_len) {
790 /* found a match */
791 bm_uidwalk_pass_add(w_src, fstep_item_src->list, fstep_item_src->list_len);
792 bm_uidwalk_pass_add(w_dst, fstep_item_dst->list, fstep_item_dst->list_len);
793
794 BLI_linklist_free_pool(fstep_item_src->list, nullptr, w_src->link_pool);
795 BLI_linklist_free_pool(fstep_item_dst->list, nullptr, w_dst->link_pool);
796
797 fstep_item_src->list = nullptr;
798 fstep_item_src->list_len = 0;
799
800 fstep_item_dst->list = nullptr;
801 fstep_item_dst->list_len = 0;
802
803 ok = true;
804 }
805 }
806 }
807
808 bm_uidwalk_facestep_end(w_src, fstep_src);
809 bm_uidwalk_facestep_end(w_dst, fstep_dst);
810
811 /* lock-step */
812 fstep_src = fstep_src->next;
813 fstep_dst = fstep_dst->next;
814 }
815
816 if (!ok) {
817 break;
818 }
819
820 found = (BLI_ghash_len(w_dst->faces_uid) == faces_src_region_len);
821 if (found) {
822 break;
823 }
824
825 /* Expensive! but some cases fails without.
826 * (also faster in other cases since it can rule-out invalid regions) */
827 bm_uidwalk_rehash(w_src);
828 bm_uidwalk_rehash(w_dst);
829 }
830
831 if (found) {
832 GHashIterator gh_iter;
833 const uint faces_result_len = BLI_ghash_len(w_dst->faces_uid);
834 uint i;
835
836 faces_result = MEM_new_array_uninitialized<BMFace *>(faces_result_len + 1, __func__);
837 GHASH_ITER_INDEX (gh_iter, w_dst->faces_uid, i) {
838 BMFace *f = static_cast<BMFace *>(BLI_ghashIterator_getKey(&gh_iter));
839 faces_result[i] = f;
840 }
841 faces_result[faces_result_len] = nullptr;
842 *r_faces_result_len = faces_result_len;
843 }
844 else {
845 *r_faces_result_len = 0;
846 }
847
848finally:
849
850#ifdef USE_WALKER_REUSE
851 bm_uidwalk_clear(w_src);
852 bm_uidwalk_clear(w_dst);
853#else
854 bm_uidwalk_free(w_src);
855 bm_uidwalk_free(w_dst);
856#endif
857
858 return faces_result;
859}
860
864static void bm_face_array_visit(BMFace **faces,
865 const uint faces_len,
866 uint *r_verts_len,
867 bool visit_faces)
868{
869 uint verts_len = 0;
870 uint i;
871 for (i = 0; i < faces_len; i++) {
872 BMFace *f = faces[i];
873 BMLoop *l_iter, *l_first;
874 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
875 do {
876 if (r_verts_len) {
877 if (!BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) {
878 verts_len += 1;
879 }
880 }
881
884 } while ((l_iter = l_iter->next) != l_first);
885
886 if (visit_faces) {
888 }
889 }
890
891 if (r_verts_len) {
892 *r_verts_len = verts_len;
893 }
894}
895
896#ifdef USE_PIVOT_SEARCH
897
898/* -------------------------------------------------------------------- */
901
902/* signed user id */
904
906{
907 return (a < 0) ? -a : a;
908}
909
911{
912 if (e->l->radial_next != e->l) {
913 BMLoop *l_iter = e->l;
914 do {
915 if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
916 return true;
917 }
918 } while ((l_iter = l_iter->radial_next) != e->l);
919 return false;
920 }
921 /* boundary */
922 return true;
923}
924
926 BMEdge *e_test,
927 BMEdge **r_e_pivot_best,
928 SUID_Int e_pivot_best_id[2])
929{
930 SUID_Int e_pivot_test_id[2];
931
932 e_pivot_test_id[0] = gh.lookup_default(e_test->v1, 0);
933 e_pivot_test_id[1] = gh.lookup_default(e_test->v2, 0);
934 if (e_pivot_test_id[0] > e_pivot_test_id[1]) {
935 std::swap(e_pivot_test_id[0], e_pivot_test_id[1]);
936 }
937
938 if ((*r_e_pivot_best == nullptr) ||
939 ((e_pivot_best_id[0] != e_pivot_test_id[0]) ? (e_pivot_best_id[0] < e_pivot_test_id[0]) :
940 (e_pivot_best_id[1] < e_pivot_test_id[1])))
941 {
942 e_pivot_best_id[0] = e_pivot_test_id[0];
943 e_pivot_best_id[1] = e_pivot_test_id[1];
944
945 /* both verts are from the same pass, record this! */
946 *r_e_pivot_best = e_test;
947 }
948}
949
950/* quick id from a boundary vertex */
952{
953# define PRIME_VERT_SMALL_A 7
954# define PRIME_VERT_SMALL_B 13
955# define PRIME_VERT_MID_A 103
956# define PRIME_VERT_MID_B 131
957
958 int tot = 0;
959 BMIter iter;
960 BMLoop *l;
962
963 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
964 const bool is_boundary_vert = (bm_edge_is_region_boundary(l->e) ||
966 id ^= l->f->len * (is_boundary_vert ? PRIME_VERT_SMALL_A : PRIME_VERT_SMALL_B);
967 tot += 1;
968 }
969
970 id ^= (tot * PRIME_VERT_MID_B);
971
972 return id ? abs_intptr(id) : 1;
973
974# undef PRIME_VERT_SMALL_A
975# undef PRIME_VERT_SMALL_B
976# undef PRIME_VERT_MID_A
977# undef PRIME_VERT_MID_B
978}
979
984{
985 BMIter eiter;
986 BMEdge *e;
987 SUID_Int tot = 0;
988 SUID_Int v_sum_face_len = 0;
989 SUID_Int v_sum_id = 0;
990 SUID_Int id;
991 SUID_Int id_min = INTPTR_MIN + 1;
992
993# define PRIME_VERT_MID_A 23
994# define PRIME_VERT_MID_B 31
995
996 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
998 BMVert *v_other = BM_edge_other_vert(e, v);
999 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1000 /* non-zero values aren't allowed... so no need to check haskey */
1001 SUID_Int v_other_id = gh.lookup_default(v_other, 0);
1002 if (v_other_id > 0) {
1003 v_sum_id += v_other_id;
1004 tot += 1;
1005
1006 /* face-count */
1007 {
1008 BMLoop *l_iter = e->l;
1009 do {
1010 if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
1011 v_sum_face_len += l_iter->f->len;
1012 }
1013 } while ((l_iter = l_iter->radial_next) != e->l);
1014 }
1015 }
1016 }
1017 }
1018 }
1019
1020 id = (tot * PRIME_VERT_MID_A);
1021 id ^= (v_sum_face_len * PRIME_VERT_MID_B);
1022 id ^= v_sum_id;
1023
1024 /* disallow 0 & min (since it can't be flipped) */
1025 id = (UNLIKELY(id == 0) ? 1 : UNLIKELY(id < id_min) ? id_min : id);
1026
1027 return abs_intptr(id);
1028
1029# undef PRIME_VERT_MID_A
1030# undef PRIME_VERT_MID_B
1031}
1032
1041 uint faces_region_len,
1042 uint verts_region_len,
1043 uint *r_depth)
1044{
1045 /* NOTE: keep deterministic where possible (geometry order independent)
1046 * this function assumed all visit faces & edges are tagged */
1047
1048 BLI_LINKSTACK_DECLARE(vert_queue_prev, BMVert *);
1049 BLI_LINKSTACK_DECLARE(vert_queue_next, BMVert *);
1050
1052 uint i;
1053
1054 BMEdge *e_pivot = nullptr;
1055 /* pick any non-boundary edge (not ideal) */
1056 BMEdge *e_pivot_fallback = nullptr;
1057
1058 SUID_Int pass = 0;
1059
1060 /* total verts in 'gs' we have visited - aka - not v_init_none */
1061 uint vert_queue_used = 0;
1062
1063 BLI_LINKSTACK_INIT(vert_queue_prev);
1064 BLI_LINKSTACK_INIT(vert_queue_next);
1065
1066 /* face-verts */
1067 for (i = 0; i < faces_region_len; i++) {
1068 BMFace *f = faces_region[i];
1069
1070 BMLoop *l_iter, *l_first;
1071 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1072 do {
1073 BMEdge *e = l_iter->e;
1075 uint j;
1076 for (j = 0; j < 2; j++) {
1077 BMVert *v = (&e->v1)[j];
1078 gh.lookup_or_add_cb(v, [&]() {
1080 BLI_LINKSTACK_PUSH(vert_queue_prev, v);
1081 vert_queue_used += 1;
1082 return v_id;
1083 });
1084 }
1085 }
1086 else {
1087 /* Use in case (depth == 0), no interior verts. */
1088 e_pivot_fallback = e;
1089 }
1090 } while ((l_iter = l_iter->next) != l_first);
1091 }
1092
1093 while (BLI_LINKSTACK_SIZE(vert_queue_prev)) {
1094 BMVert *v;
1095 while ((v = BLI_LINKSTACK_POP(vert_queue_prev))) {
1096 BMIter eiter;
1097 BMEdge *e;
1098 BLI_assert(gh.lookup(v) > 0);
1099 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1101 BMVert *v_other = BM_edge_other_vert(e, v);
1102 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1103 gh.lookup_or_add_cb(v_other, [&]() {
1104 /* add as negative, so we know not to read from them this pass */
1105 const SUID_Int v_id_other = -bm_face_region_vert_pass_id(gh, v_other);
1106 BLI_LINKSTACK_PUSH(vert_queue_next, v_other);
1107 vert_queue_used += 1;
1108 return v_id_other;
1109 });
1110 }
1111 }
1112 }
1113 }
1114
1115 /* flip all the newly added hashes to positive */
1116 {
1117 LinkNode *v_link;
1118 for (v_link = vert_queue_next; v_link; v_link = v_link->next) {
1119 SUID_Int &v_id = gh.lookup(static_cast<BMVert *>(v_link->link));
1120 v_id = -v_id;
1121 BLI_assert(v_id > 0);
1122 }
1123 }
1124
1125 BLI_LINKSTACK_SWAP(vert_queue_prev, vert_queue_next);
1126 pass += 1;
1127
1128 if (vert_queue_used == verts_region_len) {
1129 break;
1130 }
1131 }
1132
1133 if (BLI_LINKSTACK_SIZE(vert_queue_prev) >= 2) {
1134 /* common case - we managed to find some interior verts */
1135 LinkNode *v_link;
1136 BMEdge *e_pivot_best = nullptr;
1137 SUID_Int e_pivot_best_id[2] = {0, 0};
1138
1139 /* temp untag, so we can quickly know what other verts are in this last pass */
1140 for (v_link = vert_queue_prev; v_link; v_link = v_link->next) {
1141 BMVert *v = static_cast<BMVert *>(v_link->link);
1143 }
1144
1145 /* restore correct tagging */
1146 for (v_link = vert_queue_prev; v_link; v_link = v_link->next) {
1147 BMIter eiter;
1148 BMEdge *e_test;
1149
1150 BMVert *v = static_cast<BMVert *>(v_link->link);
1152
1153 BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) {
1154 if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) {
1155 BMVert *v_other = BM_edge_other_vert(e_test, v);
1156 if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == false) {
1157 bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id);
1158 }
1159 }
1160 }
1161 }
1162
1163 e_pivot = e_pivot_best;
1164 }
1165
1166 if ((e_pivot == nullptr) && BLI_LINKSTACK_SIZE(vert_queue_prev)) {
1167 /* find the best single edge */
1168 BMEdge *e_pivot_best = nullptr;
1169 SUID_Int e_pivot_best_id[2] = {0, 0};
1170
1171 LinkNode *v_link;
1172
1173 /* reduce a pass since we're having to step into a previous passes vert,
1174 * and will be closer to the boundary */
1175 BLI_assert(pass != 0);
1176 pass -= 1;
1177
1178 for (v_link = vert_queue_prev; v_link; v_link = v_link->next) {
1179 BMVert *v = static_cast<BMVert *>(v_link->link);
1180
1181 BMIter eiter;
1182 BMEdge *e_test;
1183 BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) {
1184 if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) {
1185 BMVert *v_other = BM_edge_other_vert(e_test, v);
1186 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1187 bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id);
1188 }
1189 }
1190 }
1191 }
1192
1193 e_pivot = e_pivot_best;
1194 }
1195
1196 BLI_LINKSTACK_FREE(vert_queue_prev);
1197 BLI_LINKSTACK_FREE(vert_queue_next);
1198
1199 if (e_pivot == nullptr) {
1200# ifdef DEBUG_PRINT
1201 printf("%s: using fallback edge!\n", __func__);
1202# endif
1203 e_pivot = e_pivot_fallback;
1204 pass = 0;
1205 }
1206
1207 *r_depth = uint(pass);
1208
1209 return e_pivot;
1210}
1211
1213
1214#endif /* USE_PIVOT_SEARCH */
1215
1216/* Quick UID pass - identify candidates */
1217
1218#ifdef USE_PIVOT_FASTMATCH
1219
1220/* -------------------------------------------------------------------- */
1223
1225
1227{
1228 BMIter eiter;
1229 BMEdge *e;
1230 UIDFashMatch e_num = 0, f_num = 0, l_num = 0;
1231
1232# define PRIME_EDGE 7
1233# define PRIME_FACE 31
1234# define PRIME_LOOP 61
1235
1236 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1237 if (!BM_edge_is_wire(e)) {
1238 BMLoop *l_iter = e->l;
1239 e_num += 1;
1240 do {
1241 f_num += 1;
1242 l_num += uint(l_iter->f->len);
1243 } while ((l_iter = l_iter->radial_next) != e->l);
1244 }
1245 }
1246
1247 return ((e_num * PRIME_EDGE) ^ (f_num * PRIME_FACE) * (l_num * PRIME_LOOP));
1248
1249# undef PRIME_EDGE
1250# undef PRIME_FACE
1251# undef PRIME_LOOP
1252}
1253
1255{
1256 UIDFashMatch *id_prev;
1257 UIDFashMatch *id_curr;
1258 uint pass, i;
1259 BMVert *v;
1260 BMIter iter;
1261
1264
1265 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1266 id_prev[i] = bm_vert_fasthash_single(v);
1267 }
1268
1269 for (pass = 0; pass < depth; pass++) {
1270 BMEdge *e;
1271
1272 memcpy(id_curr, id_prev, sizeof(*id_prev) * uint(bm->totvert));
1273
1274 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1275 if (BM_edge_is_wire(e) == false) {
1276 const int i1 = BM_elem_index_get(e->v1);
1277 const int i2 = BM_elem_index_get(e->v2);
1278
1279 id_curr[i1] += id_prev[i2];
1280 id_curr[i2] += id_prev[i1];
1281 }
1282 }
1283 }
1284 MEM_delete(id_prev);
1285
1286 return id_curr;
1287}
1288
1290 const BMEdge *e,
1291 UIDFashMatch e_fm[2])
1292{
1293 e_fm[0] = fm[BM_elem_index_get(e->v1)];
1294 e_fm[1] = fm[BM_elem_index_get(e->v2)];
1295
1296 if (e_fm[0] > e_fm[1]) {
1297 std::swap(e_fm[0], e_fm[1]);
1298 }
1299}
1300
1301static bool bm_vert_fasthash_edge_is_match(UIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b)
1302{
1303 UIDFashMatch e_a_fm[2];
1304 UIDFashMatch e_b_fm[2];
1305
1306 bm_vert_fasthash_edge_order(fm, e_a, e_a_fm);
1307 bm_vert_fasthash_edge_order(fm, e_b, e_b_fm);
1308
1309 return ((e_a_fm[0] == e_b_fm[0]) && (e_a_fm[1] == e_b_fm[1]));
1310}
1311
1313{
1314 MEM_delete(fm);
1315}
1316
1318
1319#endif /* USE_PIVOT_FASTMATCH */
1320
1322 BMFace **faces_region,
1323 uint faces_region_len,
1324 ListBaseT<LinkData> *r_face_regions)
1325{
1326 BMEdge *e_src;
1327 BMEdge *e_dst;
1328 BMIter iter;
1329 uint verts_region_len = 0;
1330 uint faces_result_len = 0;
1331 /* number of steps from e_src to a boundary vert */
1332 uint depth;
1333
1334#ifdef USE_WALKER_REUSE
1335 UIDWalk w_src, w_dst;
1336#endif
1337
1338#ifdef USE_PIVOT_FASTMATCH
1339 UIDFashMatch *fm;
1340#endif
1341
1342#ifdef DEBUG_PRINT
1343 int search_num = 0;
1344#endif
1345
1346#ifdef DEBUG_TIME
1347 TIMEIT_START(region_match);
1348#endif
1349
1350 /* initialize visited verts */
1352 bm_face_array_visit(faces_region, faces_region_len, &verts_region_len, true);
1353
1354 /* needed for 'ghashutil_bmelem_indexhash' */
1356
1357#ifdef USE_PIVOT_SEARCH
1358 e_src = bm_face_region_pivot_edge_find(faces_region, faces_region_len, verts_region_len, &depth);
1359
1360/* see which edge is added */
1361# if 0
1363 if (e_src) {
1365 }
1366# endif
1367
1368#else
1369 /* quick test only! */
1370 e_src = BM_mesh_active_edge_get(bm);
1371#endif
1372
1373 if (e_src == nullptr) {
1374#ifdef DEBUG_PRINT
1375 printf("Couldn't find 'e_src'");
1376#endif
1377 return 0;
1378 }
1379
1380 r_face_regions->clear_no_delete();
1381
1382#ifdef USE_PIVOT_FASTMATCH
1383 if (depth > 0) {
1384 fm = bm_vert_fasthash_create(bm, depth);
1385 }
1386 else {
1387 fm = nullptr;
1388 }
1389#endif
1390
1391#ifdef USE_WALKER_REUSE
1392 bm_uidwalk_init(&w_src, faces_region_len, verts_region_len);
1393 bm_uidwalk_init(&w_dst, faces_region_len, verts_region_len);
1394#endif
1395
1396 BM_ITER_MESH (e_dst, &iter, bm, BM_EDGES_OF_MESH) {
1397 BMFace **faces_result;
1398 uint faces_result_len_out;
1399
1400 if (BM_elem_flag_test(e_dst, BM_ELEM_TAG) || BM_edge_is_wire(e_dst)) {
1401 continue;
1402 }
1403
1404#ifdef USE_PIVOT_FASTMATCH
1405 if (fm && !bm_vert_fasthash_edge_is_match(fm, e_src, e_dst)) {
1406 continue;
1407 }
1408#endif
1409
1410#ifdef DEBUG_PRINT
1411 search_num += 1;
1412#endif
1413
1414 faces_result = bm_mesh_region_match_pair(
1415#ifdef USE_WALKER_REUSE
1416 &w_src,
1417 &w_dst,
1418#endif
1419 e_src,
1420 e_dst,
1421 faces_region_len,
1422 verts_region_len,
1423 &faces_result_len_out);
1424
1425 /* tag verts as visited */
1426 if (faces_result) {
1427 LinkData *link;
1428
1429 bm_face_array_visit(faces_result, faces_result_len_out, nullptr, false);
1430
1431 link = BLI_genericNodeN(faces_result);
1432 BLI_addtail(r_face_regions, link);
1433 faces_result_len += 1;
1434 }
1435 }
1436
1437#ifdef USE_WALKER_REUSE
1438 bm_uidwalk_free(&w_src);
1439 bm_uidwalk_free(&w_dst);
1440#else
1441 (void)bm_uidwalk_clear;
1442#endif
1443
1444#ifdef USE_PIVOT_FASTMATCH
1445 if (fm) {
1447 }
1448#endif
1449
1450#ifdef DEBUG_PRINT
1451 printf("%s: search: %d, found %d\n", __func__, search_num, faces_result_len);
1452#endif
1453
1454#ifdef DEBUG_TIME
1455 TIMEIT_END(region_match);
1456#endif
1457
1458 return int(faces_result_len);
1459}
1460
1461} // namespace blender
#define INTPTR_MIN
#define GHASH_ITER(gh_iter_, ghash_)
Definition BLI_ghash.hh:320
#define GHASH_ITER_INDEX(gh_iter_, ghash_, i_)
Definition BLI_ghash.hh:324
Platform independent time functions.
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
#define TIMEIT_END(var)
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define UNLIKELY(x)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_test_bool(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)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define BM_select_history_store(bm, ele)
#define MEM_realloc_uninitialized(vmemh, len)
#define PRIME_LOOP
#define PRIME_VERT_MID_B
#define PRIME_FACE_MID
#define USE_WALKER_REUSE
#define PRIME_VERT_MID
#define PRIME_FACE
#define PRIME_EDGE
#define PRIME_FACE_SMALL
#define PRIME_VERT_LARGE
#define PRIME_VERT_SMALL
#define PRIME_VERT_MID_A
#define PRIME_VERT_INIT
#define PRIME_VERT_SMALL_A
#define PRIME_FACE_LARGE
#define PRIME_VERT_SMALL_B
const T * begin() const
Definition BLI_array.hh:332
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
Value lookup_default(const Key &key, const Value &default_value) const
Definition BLI_map.hh:570
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
bool is_empty() const
Definition BLI_set.hh:614
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
BLI_INLINE intptr_t abs_intptr(intptr_t a)
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)
uintptr_t UIDFashMatch
unsigned __int64 uint64_t
Definition BKE_text.h:91
int BM_edge_face_count(const BMEdge *e)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
static uint ghashutil_bmelem_indexhash(const void *key)
BLI_INLINE void * BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.hh:297
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void bm_uidwalk_rehash_facelinks(UIDWalk *uidwalk, LinkNode *faces, const uint faces_len, const bool is_init)
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GHash * BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:682
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int BM_mesh_region_match(BMesh *bm, BMFace **faces_region, uint faces_region_len, ListBaseT< LinkData > *r_face_regions)
void BLI_addhead(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:98
static bool bm_vert_fasthash_edge_is_match(UIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
BLI_INLINE void ** BLI_ghashIterator_getValue_p(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.hh:305
BLI_INLINE bool bm_uidwalk_face_test(UIDWalk *uidwalk, BMFace *f)
static GHash * ghash_bmelem_new(const char *info)
static void bm_uidwalk_facestep_free(UIDWalk *uidwalk, UIDFaceStep *fstep)
static void bm_uidwalk_rehash_reserve(UIDWalk *uidwalk, uint rehash_store_len_new)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
static bool bm_edge_is_region_boundary(BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE bool bm_uidwalk_face_lookup(UIDWalk *uidwalk, BMFace *f, UID_Int *r_uid)
static void bm_uidwalk_clear(UIDWalk *uidwalk)
static uint bm_uidwalk_init_from_edge(UIDWalk *uidwalk, BMEdge *e)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void bm_uidwalk_init(UIDWalk *uidwalk, const uint faces_src_region_len, const uint verts_src_region_len)
static UIDFashMatch * bm_vert_fasthash_create(BMesh *bm, const uint depth)
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:711
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
BMEdge * BM_mesh_active_edge_get(BMesh *bm)
void * BLI_pophead(ListBase *listbase) ATTR_NONNULL(1)
Definition listbase.cc:259
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.hh:301
void ** BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:749
static void bm_uidwalk_free(UIDWalk *uidwalk)
static SUID_Int bm_face_region_vert_pass_id(const Map< BMVert *, SUID_Int > &gh, BMVert *v)
static bool bm_vert_is_uid_connect(UIDWalk *uidwalk, BMVert *v)
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
static void bm_uidwalk_facestep_end(UIDWalk *uidwalk, UIDFaceStep *fstep)
static SUID_Int bm_face_region_vert_boundary_id(BMVert *v)
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:866
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
static int facestep_sort(const void *a, const void *b)
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:756
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
void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool)
void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:861
static void bm_face_region_pivot_edge_use_best(const Map< BMVert *, SUID_Int > &gh, BMEdge *e_test, BMEdge **r_e_pivot_best, SUID_Int e_pivot_best_id[2])
static void bm_vert_fasthash_destroy(UIDFashMatch *fm)
LinkData * BLI_genericNodeN(void *data)
Definition listbase.cc:936
void BLI_mempool_clear(BLI_mempool *pool) ATTR_NONNULL(1)
static void bm_uidwalk_pass_add(UIDWalk *uidwalk, LinkNode *faces_pass, const uint faces_pass_len)
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:706
static UID_Int bm_uidwalk_calc_vert_uid(UIDWalk *uidwalk, BMVert *v)
static void bm_face_array_visit(BMFace **faces, const uint faces_len, uint *r_verts_len, bool visit_faces)
_W64 unsigned int uintptr_t
Definition BKE_text.h:120
void void BLI_listbase_sort(ListBase *listbase, int(*cmp)(const void *, const void *)) ATTR_NONNULL(1
Definition listbase.cc:319
static UIDFashMatch bm_vert_fasthash_single(BMVert *v)
static BMFace ** bm_mesh_region_match_pair(UIDWalk *w_src, UIDWalk *w_dst, BMEdge *e_src, BMEdge *e_dst, const uint faces_src_region_len, const uint verts_src_region_len, uint *r_faces_result_len)
static void bm_vert_fasthash_edge_order(const UIDFashMatch *fm, const BMEdge *e, UIDFashMatch e_fm[2])
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
static bool bm_uidwalk_facestep_begin(UIDWalk *uidwalk, UIDFaceStep *fstep)
@ BLI_MEMPOOL_NOP
static bool ghashutil_bmelem_indexcmp(const void *a, const void *b)
Set< BMFace *, 4, DefaultProbingStrategy, BMElemIndexHash, BMElemIndexEq > BMFaceIndexSet
static GHash * ghash_bmelem_new_ex(const char *info, const uint nentries_reserve)
BLI_INLINE bool bm_uidwalk_vert_lookup(UIDWalk *uidwalk, BMVert *v, UID_Int *r_uid)
void BM_select_history_clear(BMesh *bm)
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
uintptr_t UID_Int
int BLI_linklist_count(const LinkNode *list) ATTR_WARN_UNUSED_RESULT
static void bm_uidwalk_rehash(UIDWalk *uidwalk)
intptr_t SUID_Int
bool BLI_ghash_haskey(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:825
static UID_Int bm_uidwalk_calc_face_uid(UIDWalk *uidwalk, BMFace *f)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static BMEdge * bm_face_region_pivot_edge_find(BMFace **faces_region, uint faces_region_len, uint verts_region_len, uint *r_depth)
_W64 int intptr_t
Definition BKE_text.h:119
bool operator()(const BMElemT *a, const BMElemT *b) const
uint64_t operator()(const BMElemT *ele) const
struct BMLoop * next
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct LinkNode * next
ListBaseT< UIDFaceStepItem > items
ListBaseT< UIDFaceStep > faces_step
BLI_mempool * step_pool_items
struct blender::UIDWalk::@170342221156106240117130306006002120347326230076 cache
BLI_mempool * link_pool