39#define USE_WALKER_REUSE
44#define USE_PIVOT_FASTMATCH
47#define USE_PIVOT_SEARCH
65#define PRIME_VERT_INIT 100003
77 template<
typename BMElemT>
bool operator()(
const BMElemT *a,
const BMElemT *
b)
const
159 *r_uid =
reinterpret_cast<UID_Int>(*ret);
170 *r_uid =
reinterpret_cast<UID_Int>(*ret);
198 const uint faces_src_region_len,
199 const uint verts_src_region_len)
212 uidwalk->
cache.rehash_store =
nullptr;
213 uidwalk->
cache.rehash_store_len = 0;
262 MEM_SAFE_DELETE(uidwalk->
cache.rehash_store);
271#define PRIME_VERT_SMALL 7
272#define PRIME_VERT_MID 43
273#define PRIME_VERT_LARGE 1031
275#define PRIME_FACE_SMALL 13
276#define PRIME_FACE_MID 53
316#undef PRIME_VERT_SMALL
318#undef PRIME_VERT_LARGE
320#undef PRIME_FACE_SMALL
326#define PRIME_VERT_SMALL 11
328#define PRIME_FACE_SMALL 17
329#define PRIME_FACE_LARGE 1013
345 }
while ((l_iter = l_iter->
next) != l_first);
361 }
while ((l_iter_radial = l_iter_radial->
radial_next) != l_iter);
363 }
while ((l_iter = l_iter->
next) != l_first);
368#undef PRIME_VERT_SMALL
370#undef PRIME_FACE_SMALL
371#undef PRIME_FACE_LARGE
376 if (rehash_store_len_new > uidwalk->
cache.rehash_store_len) [[unlikely]] {
378 rehash_store_len_new *= 2;
380 uidwalk->
cache.rehash_store, rehash_store_len_new *
sizeof(*uidwalk->
cache.rehash_store)));
381 uidwalk->
cache.rehash_store_len = rehash_store_len_new;
398 uid_store = uidwalk->
cache.rehash_store;
409 *(
reinterpret_cast<UID_Int *
>(uid_p)) = uid_store[i++];
421 *(
reinterpret_cast<UID_Int *
>(uid_p)) = uid_store[i++];
427 const uint faces_len,
435 uid_store = uidwalk->
cache.rehash_store;
438 for (f_link = faces; f_link; f_link = f_link->
next) {
445 for (f_link = faces; f_link; f_link = f_link->
next) {
451 for (f_link = faces; f_link; f_link = f_link->
next) {
454 *(
reinterpret_cast<UID_Int *
>(uid_p)) = uid_store[i++];
476 GHash *verts_uid_pass;
496 fstep->
faces =
nullptr;
497 fstep->
items.clear_no_delete();
499 for (f_link = faces_pass; f_link; f_link = f_link->
next) {
512 *val_p =
reinterpret_cast<void *
>(uid);
520 !faces_step_next->
contains(l_iter_radial->
f) &&
523 faces_step_next->
add(l_iter_radial->
f);
528 }
while ((l_iter_radial = l_iter_radial->
radial_next) != l_iter);
530 }
while ((l_iter = l_iter->
next) != l_first);
554 uint fstep_num = 0, i = 0;
566 return f1->len < f2->len;
579 for (i = 0; i < f_arr_len;) {
581 const uint i_init = i;
582 const int f_len = f_arr[i]->len;
586 }
while (i < f_arr_len && (f_len == f_arr[i]->
len));
596#undef PRIME_VERT_INIT
608 return (fstep_a->
uid > fstep_b->
uid) ? 1 : 0;
617 LinkNode *f_link, *f_link_next, **f_link_prev_p;
623 f_link_prev_p = &fstep->
faces;
624 for (f_link = fstep->
faces; f_link; f_link = f_link_next) {
626 f_link_next = f_link->
next;
646 fstep_item->
uid = uid;
647 fstep_item->
list =
nullptr;
654 f_link_prev_p = &f_link->
next;
657 *f_link_prev_p = f_link->
next;
686 for (f_link = fstep->
faces; f_link; f_link = f_link_next) {
687 f_link_next = f_link->
next;
711 const uint faces_src_region_len,
712 const uint verts_src_region_len,
713 uint *r_faces_result_len)
715#ifndef USE_WALKER_REUSE
717 UIDWalk *w_src = &w_src_, *w_dst = &w_dst_;
719 BMFace **faces_result =
nullptr;
724#ifndef USE_WALKER_REUSE
729 w_src->use_face_isolate =
true;
745 UIDFaceStep *fstep_src = w_src->faces_step.first();
754 if (fstep_src->
faces ==
nullptr) {
759 fstep_src = fstep_src_next;
760 fstep_dst = fstep_dst_next;
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)
776 while ((fstep_item_dst !=
nullptr) && (fstep_item_dst->
uid < fstep_item_src->
uid)) {
777 fstep_item_dst = fstep_item_dst->
next;
780 if ((fstep_item_dst ==
nullptr) || (fstep_item_src->
uid != fstep_item_dst->
uid) ||
797 fstep_item_src->
list =
nullptr;
800 fstep_item_dst->
list =
nullptr;
812 fstep_src = fstep_src->
next;
813 fstep_dst = fstep_dst->
next;
841 faces_result[faces_result_len] =
nullptr;
842 *r_faces_result_len = faces_result_len;
845 *r_faces_result_len = 0;
850#ifdef USE_WALKER_REUSE
865 const uint faces_len,
871 for (i = 0; i < faces_len; i++) {
884 }
while ((l_iter = l_iter->
next) != l_first);
892 *r_verts_len = verts_len;
896#ifdef USE_PIVOT_SEARCH
907 return (a < 0) ? -a : a;
912 if (
e->l->radial_next !=
e->l) {
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]);
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])))
942 e_pivot_best_id[0] = e_pivot_test_id[0];
943 e_pivot_best_id[1] = e_pivot_test_id[1];
946 *r_e_pivot_best = e_test;
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
974# undef PRIME_VERT_SMALL_A
975# undef PRIME_VERT_SMALL_B
976# undef PRIME_VERT_MID_A
977# undef PRIME_VERT_MID_B
993# define PRIME_VERT_MID_A 23
994# define PRIME_VERT_MID_B 31
1002 if (v_other_id > 0) {
1003 v_sum_id += v_other_id;
1011 v_sum_face_len += l_iter->
f->
len;
1029# undef PRIME_VERT_MID_A
1030# undef PRIME_VERT_MID_B
1041 uint faces_region_len,
1042 uint verts_region_len,
1054 BMEdge *e_pivot =
nullptr;
1056 BMEdge *e_pivot_fallback =
nullptr;
1061 uint vert_queue_used = 0;
1067 for (i = 0; i < faces_region_len; i++) {
1068 BMFace *f = faces_region[i];
1070 BMLoop *l_iter, *l_first;
1076 for (j = 0; j < 2; j++) {
1081 vert_queue_used += 1;
1088 e_pivot_fallback =
e;
1090 }
while ((l_iter = l_iter->
next) != l_first);
1107 vert_queue_used += 1;
1118 for (v_link = vert_queue_next; v_link; v_link = v_link->
next) {
1128 if (vert_queue_used == verts_region_len) {
1136 BMEdge *e_pivot_best =
nullptr;
1137 SUID_Int e_pivot_best_id[2] = {0, 0};
1140 for (v_link = vert_queue_prev; v_link; v_link = v_link->
next) {
1146 for (v_link = vert_queue_prev; v_link; v_link = v_link->
next) {
1163 e_pivot = e_pivot_best;
1168 BMEdge *e_pivot_best =
nullptr;
1169 SUID_Int e_pivot_best_id[2] = {0, 0};
1178 for (v_link = vert_queue_prev; v_link; v_link = v_link->
next) {
1193 e_pivot = e_pivot_best;
1199 if (e_pivot ==
nullptr) {
1201 printf(
"%s: using fallback edge!\n", __func__);
1203 e_pivot = e_pivot_fallback;
1207 *r_depth =
uint(pass);
1218#ifdef USE_PIVOT_FASTMATCH
1232# define PRIME_EDGE 7
1233# define PRIME_FACE 31
1234# define PRIME_LOOP 61
1269 for (pass = 0; pass < depth; pass++) {
1272 memcpy(id_curr, id_prev,
sizeof(*id_prev) *
uint(
bm->
totvert));
1279 id_curr[i1] += id_prev[i2];
1280 id_curr[i2] += id_prev[i1];
1284 MEM_delete(id_prev);
1296 if (e_fm[0] > e_fm[1]) {
1297 std::swap(e_fm[0], e_fm[1]);
1309 return ((e_a_fm[0] == e_b_fm[0]) && (e_a_fm[1] == e_b_fm[1]));
1323 uint faces_region_len,
1324 ListBaseT<LinkData> *r_face_regions)
1329 uint verts_region_len = 0;
1330 uint faces_result_len = 0;
1334#ifdef USE_WALKER_REUSE
1338#ifdef USE_PIVOT_FASTMATCH
1357#ifdef USE_PIVOT_SEARCH
1373 if (e_src ==
nullptr) {
1375 printf(
"Couldn't find 'e_src'");
1380 r_face_regions->clear_no_delete();
1382#ifdef USE_PIVOT_FASTMATCH
1391#ifdef USE_WALKER_REUSE
1398 uint faces_result_len_out;
1404#ifdef USE_PIVOT_FASTMATCH
1423 &faces_result_len_out);
1433 faces_result_len += 1;
1437#ifdef USE_WALKER_REUSE
1444#ifdef USE_PIVOT_FASTMATCH
1451 printf(
"%s: search: %d, found %d\n", __func__, search_num, faces_result_len);
1458 return int(faces_result_len);
#define GHASH_ITER(gh_iter_, ghash_)
#define GHASH_ITER_INDEX(gh_iter_, ghash_, i_)
BLI_LINKSTACK_*** wrapper macros for using a LinkNode to store a stack of pointers,...
#define BLI_LINKSTACK_PUSH(var, ptr)
#define BLI_LINKSTACK_DECLARE(var, type)
#define BLI_LINKSTACK_SIZE(var)
#define BLI_LINKSTACK_FREE(var)
#define BLI_LINKSTACK_INIT(var)
#define BLI_LINKSTACK_POP(var)
#define BLI_LINKSTACK_SWAP(var_a, var_b)
Platform independent time functions.
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
Read Blender memory allocation and freeing.
#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_VERT_SMALL_A
#define PRIME_VERT_SMALL_B
const Value & lookup(const Key &key) const
Value lookup_default(const Key &key, const Value &default_value) const
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
bool contains(const Key &key) const
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
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)
unsigned __int64 uint64_t
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
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
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)
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
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)
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)
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
void ** BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
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)
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
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
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)
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)
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
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
void void BLI_listbase_sort(ListBase *listbase, int(*cmp)(const void *, const void *)) ATTR_NONNULL(1
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)
static bool bm_uidwalk_facestep_begin(UIDWalk *uidwalk, UIDFaceStep *fstep)
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)
int BLI_linklist_count(const LinkNode *list) ATTR_WARN_UNUSED_RESULT
static void bm_uidwalk_rehash(UIDWalk *uidwalk)
bool BLI_ghash_haskey(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
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)
bool operator()(const BMElemT *a, const BMElemT *b) const
uint64_t operator()(const BMElemT *ele) const
struct BMLoop * radial_next
ListBaseT< UIDFaceStepItem > items
BMFaceIndexSet * faces_step
ListBaseT< UIDFaceStep > faces_step
BLI_mempool * step_pool_items
struct blender::UIDWalk::@170342221156106240117130306006002120347326230076 cache