diff options
author | Campbell Barton <ideasman42@gmail.com> | 2019-04-17 07:17:24 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2019-04-17 07:21:24 +0300 |
commit | e12c08e8d170b7ca40f204a5b0423c23a9fbc2c1 (patch) | |
tree | 8cf3453d12edb177a218ef8009357518ec6cab6a /source/blender/bmesh/tools/bmesh_region_match.c | |
parent | b3dabc200a4b0399ec6b81f2ff2730d07b44fcaa (diff) |
ClangFormat: apply to source, most of intern
Apply clang format as proposed in T53211.
For details on usage and instructions for migrating branches
without conflicts, see:
https://wiki.blender.org/wiki/Tools/ClangFormat
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_region_match.c')
-rw-r--r-- | source/blender/bmesh/tools/bmesh_region_match.c | 2183 |
1 files changed, 1075 insertions, 1108 deletions
diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c index a89c41eecc0..6ddbaa6bb2e 100644 --- a/source/blender/bmesh/tools/bmesh_region_match.c +++ b/source/blender/bmesh/tools/bmesh_region_match.c @@ -43,7 +43,7 @@ #include "bmesh.h" -#include "tools/bmesh_region_match.h" /* own incldue */ +#include "tools/bmesh_region_match.h" /* own incldue */ /* avoid re-creating ghash and pools for each search */ #define USE_WALKER_REUSE @@ -66,7 +66,6 @@ #include "BLI_strict_flags.h" - /* -------------------------------------------------------------------- */ /* UUID-Walk API */ @@ -79,261 +78,251 @@ typedef uintptr_t UUID_Int; typedef struct UUIDWalk { - /* List of faces we can step onto (UUIDFaceStep's) */ - ListBase faces_step; + /* List of faces we can step onto (UUIDFaceStep's) */ + ListBase faces_step; - /* Face & Vert UUID's */ - GHash *verts_uuid; - GHash *faces_uuid; + /* Face & Vert UUID's */ + GHash *verts_uuid; + GHash *faces_uuid; - /* memory pool for LinkNode's */ - BLI_mempool *link_pool; + /* memory pool for LinkNode's */ + BLI_mempool *link_pool; - /* memory pool for LinkBase's */ - BLI_mempool *lbase_pool; + /* memory pool for LinkBase's */ + BLI_mempool *lbase_pool; - /* memory pool for UUIDFaceStep's */ - BLI_mempool *step_pool; - BLI_mempool *step_pool_items; + /* memory pool for UUIDFaceStep's */ + BLI_mempool *step_pool; + BLI_mempool *step_pool_items; - /* Optionaly use face-tag to isolate search */ - bool use_face_isolate; + /* Optionaly use face-tag to isolate search */ + bool use_face_isolate; - /* Increment for each pass added */ - UUID_Int pass; + /* Increment for each pass added */ + UUID_Int pass; - /* runtime vars, aviod re-creating each pass */ - struct { - GHash *verts_uuid; /* BMVert -> UUID */ - GSet *faces_step; /* BMFace */ + /* runtime vars, aviod re-creating each pass */ + struct { + GHash *verts_uuid; /* BMVert -> UUID */ + GSet *faces_step; /* BMFace */ - GHash *faces_from_uuid; /* UUID -> UUIDFaceStepItem */ + GHash *faces_from_uuid; /* UUID -> UUIDFaceStepItem */ - UUID_Int *rehash_store; - uint rehash_store_len; - } cache; + UUID_Int *rehash_store; + uint rehash_store_len; + } cache; } UUIDWalk; /* stores a set of potential faces to step onto */ typedef struct UUIDFaceStep { - struct UUIDFaceStep *next, *prev; + struct UUIDFaceStep *next, *prev; - /* unsorted 'BMFace' */ - LinkNode *faces; + /* unsorted 'BMFace' */ + LinkNode *faces; - /* faces sorted into 'UUIDFaceStepItem' */ - ListBase items; + /* faces sorted into 'UUIDFaceStepItem' */ + ListBase items; } UUIDFaceStep; /* store face-lists with same uuid */ typedef struct UUIDFaceStepItem { - struct UUIDFaceStepItem *next, *prev; - uintptr_t uuid; + struct UUIDFaceStepItem *next, *prev; + uintptr_t uuid; - LinkNode *list; - uint list_len; + LinkNode *list; + uint list_len; } UUIDFaceStepItem; -BLI_INLINE bool bm_uuidwalk_face_test( - UUIDWalk *uuidwalk, BMFace *f) +BLI_INLINE bool bm_uuidwalk_face_test(UUIDWalk *uuidwalk, BMFace *f) { - if (uuidwalk->use_face_isolate) { - return BM_elem_flag_test_bool(f, BM_ELEM_TAG); - } - else { - return true; - } + if (uuidwalk->use_face_isolate) { + return BM_elem_flag_test_bool(f, BM_ELEM_TAG); + } + else { + return true; + } } -BLI_INLINE bool bm_uuidwalk_vert_lookup( - UUIDWalk *uuidwalk, BMVert *v, UUID_Int *r_uuid) +BLI_INLINE bool bm_uuidwalk_vert_lookup(UUIDWalk *uuidwalk, BMVert *v, UUID_Int *r_uuid) { - void **ret; - ret = BLI_ghash_lookup_p(uuidwalk->verts_uuid, v); - if (ret) { - *r_uuid = (UUID_Int)(*ret); - return true; - } - else { - return false; - } + void **ret; + ret = BLI_ghash_lookup_p(uuidwalk->verts_uuid, v); + if (ret) { + *r_uuid = (UUID_Int)(*ret); + return true; + } + else { + return false; + } } -BLI_INLINE bool bm_uuidwalk_face_lookup( - UUIDWalk *uuidwalk, BMFace *f, UUID_Int *r_uuid) +BLI_INLINE bool bm_uuidwalk_face_lookup(UUIDWalk *uuidwalk, BMFace *f, UUID_Int *r_uuid) { - void **ret; - ret = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f); - if (ret) { - *r_uuid = (UUID_Int)(*ret); - return true; - } - else { - return false; - } + void **ret; + ret = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f); + if (ret) { + *r_uuid = (UUID_Int)(*ret); + return true; + } + else { + return false; + } } static uint ghashutil_bmelem_indexhash(const void *key) { - const BMElem *ele = key; - return (uint)BM_elem_index_get(ele); + const BMElem *ele = key; + return (uint)BM_elem_index_get(ele); } static bool ghashutil_bmelem_indexcmp(const void *a, const void *b) { - BLI_assert((a != b) == (BM_elem_index_get((BMElem *)a) != BM_elem_index_get((BMElem *)b))); - return (a != b); + BLI_assert((a != b) == (BM_elem_index_get((BMElem *)a) != BM_elem_index_get((BMElem *)b))); + return (a != b); } -static GHash *ghash_bmelem_new_ex( - const char *info, - const uint nentries_reserve) +static GHash *ghash_bmelem_new_ex(const char *info, const uint nentries_reserve) { - return BLI_ghash_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); + return BLI_ghash_new_ex( + ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); } -static GSet *gset_bmelem_new_ex( - const char *info, - const uint nentries_reserve) +static GSet *gset_bmelem_new_ex(const char *info, const uint nentries_reserve) { - return BLI_gset_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); + return BLI_gset_new_ex( + ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); } - static GHash *ghash_bmelem_new(const char *info) { - return ghash_bmelem_new_ex(info, 0); + return ghash_bmelem_new_ex(info, 0); } static GSet *gset_bmelem_new(const char *info) { - return gset_bmelem_new_ex(info, 0); + return gset_bmelem_new_ex(info, 0); } - -static void bm_uuidwalk_init( - UUIDWalk *uuidwalk, - const uint faces_src_region_len, - const uint verts_src_region_len) +static void bm_uuidwalk_init(UUIDWalk *uuidwalk, + const uint faces_src_region_len, + const uint verts_src_region_len) { - BLI_listbase_clear(&uuidwalk->faces_step); + BLI_listbase_clear(&uuidwalk->faces_step); - uuidwalk->verts_uuid = ghash_bmelem_new_ex(__func__, verts_src_region_len); - uuidwalk->faces_uuid = ghash_bmelem_new_ex(__func__, faces_src_region_len); + uuidwalk->verts_uuid = ghash_bmelem_new_ex(__func__, verts_src_region_len); + uuidwalk->faces_uuid = ghash_bmelem_new_ex(__func__, faces_src_region_len); - uuidwalk->cache.verts_uuid = ghash_bmelem_new(__func__); - uuidwalk->cache.faces_step = gset_bmelem_new(__func__); + uuidwalk->cache.verts_uuid = ghash_bmelem_new(__func__); + uuidwalk->cache.faces_step = gset_bmelem_new(__func__); - /* works because 'int' ghash works for intptr_t too */ - uuidwalk->cache.faces_from_uuid = BLI_ghash_int_new(__func__); + /* works because 'int' ghash works for intptr_t too */ + uuidwalk->cache.faces_from_uuid = BLI_ghash_int_new(__func__); - uuidwalk->cache.rehash_store = NULL; - uuidwalk->cache.rehash_store_len = 0; + uuidwalk->cache.rehash_store = NULL; + uuidwalk->cache.rehash_store_len = 0; - uuidwalk->use_face_isolate = false; + uuidwalk->use_face_isolate = false; - /* smaller pool's for faster clearing */ - uuidwalk->link_pool = BLI_mempool_create(sizeof(LinkNode), 64, 64, BLI_MEMPOOL_NOP); - uuidwalk->step_pool = BLI_mempool_create(sizeof(UUIDFaceStep), 64, 64, BLI_MEMPOOL_NOP); - uuidwalk->step_pool_items = BLI_mempool_create(sizeof(UUIDFaceStepItem), 64, 64, BLI_MEMPOOL_NOP); + /* smaller pool's for faster clearing */ + uuidwalk->link_pool = BLI_mempool_create(sizeof(LinkNode), 64, 64, BLI_MEMPOOL_NOP); + uuidwalk->step_pool = BLI_mempool_create(sizeof(UUIDFaceStep), 64, 64, BLI_MEMPOOL_NOP); + uuidwalk->step_pool_items = BLI_mempool_create( + sizeof(UUIDFaceStepItem), 64, 64, BLI_MEMPOOL_NOP); - uuidwalk->pass = 1; + uuidwalk->pass = 1; } -static void bm_uuidwalk_clear( - UUIDWalk *uuidwalk) +static void bm_uuidwalk_clear(UUIDWalk *uuidwalk) { - BLI_listbase_clear(&uuidwalk->faces_step); + BLI_listbase_clear(&uuidwalk->faces_step); - BLI_ghash_clear(uuidwalk->verts_uuid, NULL, NULL); - BLI_ghash_clear(uuidwalk->faces_uuid, NULL, NULL); + BLI_ghash_clear(uuidwalk->verts_uuid, NULL, NULL); + BLI_ghash_clear(uuidwalk->faces_uuid, NULL, NULL); - BLI_ghash_clear(uuidwalk->cache.verts_uuid, NULL, NULL); - BLI_gset_clear(uuidwalk->cache.faces_step, NULL); - BLI_ghash_clear(uuidwalk->cache.faces_from_uuid, NULL, NULL); + BLI_ghash_clear(uuidwalk->cache.verts_uuid, NULL, NULL); + BLI_gset_clear(uuidwalk->cache.faces_step, NULL); + BLI_ghash_clear(uuidwalk->cache.faces_from_uuid, NULL, NULL); - /* keep rehash_store as-is, for reuse */ + /* keep rehash_store as-is, for reuse */ - uuidwalk->use_face_isolate = false; + uuidwalk->use_face_isolate = false; - BLI_mempool_clear(uuidwalk->link_pool); - BLI_mempool_clear(uuidwalk->step_pool); - BLI_mempool_clear(uuidwalk->step_pool_items); + BLI_mempool_clear(uuidwalk->link_pool); + BLI_mempool_clear(uuidwalk->step_pool); + BLI_mempool_clear(uuidwalk->step_pool_items); - uuidwalk->pass = 1; + uuidwalk->pass = 1; } -static void bm_uuidwalk_free( - UUIDWalk *uuidwalk) +static void bm_uuidwalk_free(UUIDWalk *uuidwalk) { - /** - * Handled by pools - * - * - uuidwalk->faces_step - */ - - BLI_ghash_free(uuidwalk->verts_uuid, NULL, NULL); - BLI_ghash_free(uuidwalk->faces_uuid, NULL, NULL); - - /* cache */ - BLI_ghash_free(uuidwalk->cache.verts_uuid, NULL, NULL); - BLI_gset_free(uuidwalk->cache.faces_step, NULL); - BLI_ghash_free(uuidwalk->cache.faces_from_uuid, NULL, NULL); - MEM_SAFE_FREE(uuidwalk->cache.rehash_store); - - BLI_mempool_destroy(uuidwalk->link_pool); - BLI_mempool_destroy(uuidwalk->step_pool); - BLI_mempool_destroy(uuidwalk->step_pool_items); + /** + * Handled by pools + * + * - uuidwalk->faces_step + */ + + BLI_ghash_free(uuidwalk->verts_uuid, NULL, NULL); + BLI_ghash_free(uuidwalk->faces_uuid, NULL, NULL); + + /* cache */ + BLI_ghash_free(uuidwalk->cache.verts_uuid, NULL, NULL); + BLI_gset_free(uuidwalk->cache.faces_step, NULL); + BLI_ghash_free(uuidwalk->cache.faces_from_uuid, NULL, NULL); + MEM_SAFE_FREE(uuidwalk->cache.rehash_store); + + BLI_mempool_destroy(uuidwalk->link_pool); + BLI_mempool_destroy(uuidwalk->step_pool); + BLI_mempool_destroy(uuidwalk->step_pool_items); } -static UUID_Int bm_uuidwalk_calc_vert_uuid( - UUIDWalk *uuidwalk, BMVert *v) +static UUID_Int bm_uuidwalk_calc_vert_uuid(UUIDWalk *uuidwalk, BMVert *v) { -#define PRIME_VERT_SMALL 7 -#define PRIME_VERT_MID 43 -#define PRIME_VERT_LARGE 1031 - -#define PRIME_FACE_SMALL 13 -#define PRIME_FACE_MID 53 - - UUID_Int uuid; - - uuid = uuidwalk->pass * PRIME_VERT_LARGE; - - /* vert -> other */ - { - uint tot = 0; - BMIter eiter; - BMEdge *e; - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - BMVert *v_other = BM_edge_other_vert(e, v); - UUID_Int uuid_other; - if (bm_uuidwalk_vert_lookup(uuidwalk, v_other, &uuid_other)) { - uuid ^= (uuid_other * PRIME_VERT_SMALL); - tot += 1; - } - } - uuid ^= (tot * PRIME_VERT_MID); - } - - /* faces */ - { - uint tot = 0; - BMIter iter; - BMFace *f; - - BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) { - UUID_Int uuid_other; - if (bm_uuidwalk_face_lookup(uuidwalk, f, &uuid_other)) { - uuid ^= (uuid_other * PRIME_FACE_SMALL); - tot += 1; - } - } - uuid ^= (tot * PRIME_FACE_MID); - } - - return uuid; +#define PRIME_VERT_SMALL 7 +#define PRIME_VERT_MID 43 +#define PRIME_VERT_LARGE 1031 + +#define PRIME_FACE_SMALL 13 +#define PRIME_FACE_MID 53 + + UUID_Int uuid; + + uuid = uuidwalk->pass * PRIME_VERT_LARGE; + + /* vert -> other */ + { + uint tot = 0; + BMIter eiter; + BMEdge *e; + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + BMVert *v_other = BM_edge_other_vert(e, v); + UUID_Int uuid_other; + if (bm_uuidwalk_vert_lookup(uuidwalk, v_other, &uuid_other)) { + uuid ^= (uuid_other * PRIME_VERT_SMALL); + tot += 1; + } + } + uuid ^= (tot * PRIME_VERT_MID); + } + + /* faces */ + { + uint tot = 0; + BMIter iter; + BMFace *f; + + BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) { + UUID_Int uuid_other; + if (bm_uuidwalk_face_lookup(uuidwalk, f, &uuid_other)) { + uuid ^= (uuid_other * PRIME_FACE_SMALL); + tot += 1; + } + } + uuid ^= (tot * PRIME_FACE_MID); + } + + return uuid; #undef PRIME_VERT_SMALL #undef PRIME_VERT_MID @@ -343,50 +332,49 @@ static UUID_Int bm_uuidwalk_calc_vert_uuid( #undef PRIME_FACE_MID } -static UUID_Int bm_uuidwalk_calc_face_uuid( - UUIDWalk *uuidwalk, BMFace *f) +static UUID_Int bm_uuidwalk_calc_face_uuid(UUIDWalk *uuidwalk, BMFace *f) { -#define PRIME_VERT_SMALL 11 - -#define PRIME_FACE_SMALL 17 -#define PRIME_FACE_LARGE 1013 - - UUID_Int uuid; - - uuid = uuidwalk->pass * (uint)f->len * PRIME_FACE_LARGE; - - /* face-verts */ - { - BMLoop *l_iter, *l_first; - - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - UUID_Int uuid_other; - if (bm_uuidwalk_vert_lookup(uuidwalk, l_iter->v, &uuid_other)) { - uuid ^= (uuid_other * PRIME_VERT_SMALL); - } - } while ((l_iter = l_iter->next) != l_first); - } - - /* face-faces (connected by edge) */ - { - BMLoop *l_iter, *l_first; - - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - if (l_iter->radial_next != l_iter) { - BMLoop *l_iter_radial = l_iter->radial_next; - do { - UUID_Int uuid_other; - if (bm_uuidwalk_face_lookup(uuidwalk, l_iter_radial->f, &uuid_other)) { - uuid ^= (uuid_other * PRIME_FACE_SMALL); - } - } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter); - } - } while ((l_iter = l_iter->next) != l_first); - } - - return uuid; +#define PRIME_VERT_SMALL 11 + +#define PRIME_FACE_SMALL 17 +#define PRIME_FACE_LARGE 1013 + + UUID_Int uuid; + + uuid = uuidwalk->pass * (uint)f->len * PRIME_FACE_LARGE; + + /* face-verts */ + { + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + UUID_Int uuid_other; + if (bm_uuidwalk_vert_lookup(uuidwalk, l_iter->v, &uuid_other)) { + uuid ^= (uuid_other * PRIME_VERT_SMALL); + } + } while ((l_iter = l_iter->next) != l_first); + } + + /* face-faces (connected by edge) */ + { + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + if (l_iter->radial_next != l_iter) { + BMLoop *l_iter_radial = l_iter->radial_next; + do { + UUID_Int uuid_other; + if (bm_uuidwalk_face_lookup(uuidwalk, l_iter_radial->f, &uuid_other)) { + uuid ^= (uuid_other * PRIME_FACE_SMALL); + } + } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter); + } + } while ((l_iter = l_iter->next) != l_first); + } + + return uuid; #undef PRIME_VERT_SMALL @@ -394,346 +382,342 @@ static UUID_Int bm_uuidwalk_calc_face_uuid( #undef PRIME_FACE_LARGE } -static void bm_uuidwalk_rehash_reserve( - UUIDWalk *uuidwalk, uint rehash_store_len_new) +static void bm_uuidwalk_rehash_reserve(UUIDWalk *uuidwalk, uint rehash_store_len_new) { - if (UNLIKELY(rehash_store_len_new > uuidwalk->cache.rehash_store_len)) { - /* avoid re-allocs */ - rehash_store_len_new *= 2; - uuidwalk->cache.rehash_store = - MEM_reallocN(uuidwalk->cache.rehash_store, - rehash_store_len_new * sizeof(*uuidwalk->cache.rehash_store)); - uuidwalk->cache.rehash_store_len = rehash_store_len_new; - } + if (UNLIKELY(rehash_store_len_new > uuidwalk->cache.rehash_store_len)) { + /* avoid re-allocs */ + rehash_store_len_new *= 2; + uuidwalk->cache.rehash_store = MEM_reallocN(uuidwalk->cache.rehash_store, + rehash_store_len_new * + sizeof(*uuidwalk->cache.rehash_store)); + uuidwalk->cache.rehash_store_len = rehash_store_len_new; + } } /** * Re-hash all elements, delay updating so as not to create feedback loop. */ -static void bm_uuidwalk_rehash( - UUIDWalk *uuidwalk) +static void bm_uuidwalk_rehash(UUIDWalk *uuidwalk) { - GHashIterator gh_iter; - UUID_Int *uuid_store; - uint i; - - uint rehash_store_len_new = MAX2(BLI_ghash_len(uuidwalk->verts_uuid), - BLI_ghash_len(uuidwalk->faces_uuid)); - - bm_uuidwalk_rehash_reserve(uuidwalk, rehash_store_len_new); - uuid_store = uuidwalk->cache.rehash_store; - - /* verts */ - i = 0; - GHASH_ITER (gh_iter, uuidwalk->verts_uuid) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); - uuid_store[i++] = bm_uuidwalk_calc_vert_uuid(uuidwalk, v); - } - i = 0; - GHASH_ITER (gh_iter, uuidwalk->verts_uuid) { - void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter); - *((UUID_Int *)uuid_p) = uuid_store[i++]; - } - - /* faces */ - i = 0; - GHASH_ITER (gh_iter, uuidwalk->faces_uuid) { - BMFace *f = BLI_ghashIterator_getKey(&gh_iter); - uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f); - } - i = 0; - GHASH_ITER (gh_iter, uuidwalk->faces_uuid) { - void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter); - *((UUID_Int *)uuid_p) = uuid_store[i++]; - } + GHashIterator gh_iter; + UUID_Int *uuid_store; + uint i; + + uint rehash_store_len_new = MAX2(BLI_ghash_len(uuidwalk->verts_uuid), + BLI_ghash_len(uuidwalk->faces_uuid)); + + bm_uuidwalk_rehash_reserve(uuidwalk, rehash_store_len_new); + uuid_store = uuidwalk->cache.rehash_store; + + /* verts */ + i = 0; + GHASH_ITER (gh_iter, uuidwalk->verts_uuid) { + BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + uuid_store[i++] = bm_uuidwalk_calc_vert_uuid(uuidwalk, v); + } + i = 0; + GHASH_ITER (gh_iter, uuidwalk->verts_uuid) { + void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter); + *((UUID_Int *)uuid_p) = uuid_store[i++]; + } + + /* faces */ + i = 0; + GHASH_ITER (gh_iter, uuidwalk->faces_uuid) { + BMFace *f = BLI_ghashIterator_getKey(&gh_iter); + uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f); + } + i = 0; + GHASH_ITER (gh_iter, uuidwalk->faces_uuid) { + void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter); + *((UUID_Int *)uuid_p) = uuid_store[i++]; + } } -static void bm_uuidwalk_rehash_facelinks( - UUIDWalk *uuidwalk, - LinkNode *faces, const uint faces_len, - const bool is_init) +static void bm_uuidwalk_rehash_facelinks(UUIDWalk *uuidwalk, + LinkNode *faces, + const uint faces_len, + const bool is_init) { - UUID_Int *uuid_store; - LinkNode *f_link; - uint i; - - bm_uuidwalk_rehash_reserve(uuidwalk, faces_len); - uuid_store = uuidwalk->cache.rehash_store; - - i = 0; - for (f_link = faces; f_link; f_link = f_link->next) { - BMFace *f = f_link->link; - uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f); - } - - i = 0; - if (is_init) { - for (f_link = faces; f_link; f_link = f_link->next) { - BMFace *f = f_link->link; - BLI_ghash_insert(uuidwalk->faces_uuid, f, (void *)uuid_store[i++]); - } - } - else { - for (f_link = faces; f_link; f_link = f_link->next) { - BMFace *f = f_link->link; - void **uuid_p = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f); - *((UUID_Int *)uuid_p) = uuid_store[i++]; - } - } + UUID_Int *uuid_store; + LinkNode *f_link; + uint i; + + bm_uuidwalk_rehash_reserve(uuidwalk, faces_len); + uuid_store = uuidwalk->cache.rehash_store; + + i = 0; + for (f_link = faces; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f); + } + + i = 0; + if (is_init) { + for (f_link = faces; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + BLI_ghash_insert(uuidwalk->faces_uuid, f, (void *)uuid_store[i++]); + } + } + else { + for (f_link = faces; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + void **uuid_p = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f); + *((UUID_Int *)uuid_p) = uuid_store[i++]; + } + } } -static bool bm_vert_is_uuid_connect( - UUIDWalk *uuidwalk, BMVert *v) +static bool bm_vert_is_uuid_connect(UUIDWalk *uuidwalk, BMVert *v) { - BMIter eiter; - BMEdge *e; - - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - BMVert *v_other = BM_edge_other_vert(e, v); - if (BLI_ghash_haskey(uuidwalk->verts_uuid, v_other)) { - return true; - } - } - return false; + BMIter eiter; + BMEdge *e; + + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BLI_ghash_haskey(uuidwalk->verts_uuid, v_other)) { + return true; + } + } + return false; } -static void bm_uuidwalk_pass_add( - UUIDWalk *uuidwalk, LinkNode *faces_pass, const uint faces_pass_len) +static void bm_uuidwalk_pass_add(UUIDWalk *uuidwalk, + LinkNode *faces_pass, + const uint faces_pass_len) { - GHashIterator gh_iter; - GHash *verts_uuid_pass; - GSet *faces_step_next; - LinkNode *f_link; - - UUIDFaceStep *fstep; - - BLI_assert(faces_pass_len == (uint)BLI_linklist_count(faces_pass)); - - /* rehash faces now all their verts have been added */ - bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true); - - /* create verts_new */ - verts_uuid_pass = uuidwalk->cache.verts_uuid; - faces_step_next = uuidwalk->cache.faces_step; - - BLI_assert(BLI_ghash_len(verts_uuid_pass) == 0); - BLI_assert(BLI_gset_len(faces_step_next) == 0); - - /* Add the face_step data from connected faces, creating new passes */ - fstep = BLI_mempool_alloc(uuidwalk->step_pool); - BLI_addhead(&uuidwalk->faces_step, fstep); - fstep->faces = NULL; - BLI_listbase_clear(&fstep->items); - - for (f_link = faces_pass; f_link; f_link = f_link->next) { - BMFace *f = f_link->link; - BMLoop *l_iter, *l_first; - - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - /* fill verts_new */ - void **val_p; - if (!BLI_ghash_haskey(uuidwalk->verts_uuid, l_iter->v) && - !BLI_ghash_ensure_p(verts_uuid_pass, l_iter->v, &val_p) && - (bm_vert_is_uuid_connect(uuidwalk, l_iter->v) == true)) - { - const UUID_Int uuid = bm_uuidwalk_calc_vert_uuid(uuidwalk, l_iter->v); - *val_p = (void *)uuid; - } - - /* fill faces_step_next */ - if (l_iter->radial_next != l_iter) { - BMLoop *l_iter_radial = l_iter->radial_next; - do { - if (!BLI_ghash_haskey(uuidwalk->faces_uuid, l_iter_radial->f) && - !BLI_gset_haskey(faces_step_next, l_iter_radial->f) && - (bm_uuidwalk_face_test(uuidwalk, l_iter_radial->f))) - { - BLI_gset_insert(faces_step_next, l_iter_radial->f); - - /* add to fstep */ - BLI_linklist_prepend_pool(&fstep->faces, l_iter_radial->f, uuidwalk->link_pool); - } - } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter); - } - } while ((l_iter = l_iter->next) != l_first); - } - - /* faces_uuid.update(verts_new) */ - GHASH_ITER (gh_iter, verts_uuid_pass) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); - void *uuid_p = BLI_ghashIterator_getValue(&gh_iter); - BLI_ghash_insert(uuidwalk->verts_uuid, v, uuid_p); - } - - /* rehash faces now all their verts have been added */ - bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, false); - - uuidwalk->pass += 1; - - BLI_ghash_clear(uuidwalk->cache.verts_uuid, NULL, NULL); - BLI_gset_clear(uuidwalk->cache.faces_step, NULL); + GHashIterator gh_iter; + GHash *verts_uuid_pass; + GSet *faces_step_next; + LinkNode *f_link; + + UUIDFaceStep *fstep; + + BLI_assert(faces_pass_len == (uint)BLI_linklist_count(faces_pass)); + + /* rehash faces now all their verts have been added */ + bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true); + + /* create verts_new */ + verts_uuid_pass = uuidwalk->cache.verts_uuid; + faces_step_next = uuidwalk->cache.faces_step; + + BLI_assert(BLI_ghash_len(verts_uuid_pass) == 0); + BLI_assert(BLI_gset_len(faces_step_next) == 0); + + /* Add the face_step data from connected faces, creating new passes */ + fstep = BLI_mempool_alloc(uuidwalk->step_pool); + BLI_addhead(&uuidwalk->faces_step, fstep); + fstep->faces = NULL; + BLI_listbase_clear(&fstep->items); + + for (f_link = faces_pass; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + /* fill verts_new */ + void **val_p; + if (!BLI_ghash_haskey(uuidwalk->verts_uuid, l_iter->v) && + !BLI_ghash_ensure_p(verts_uuid_pass, l_iter->v, &val_p) && + (bm_vert_is_uuid_connect(uuidwalk, l_iter->v) == true)) { + const UUID_Int uuid = bm_uuidwalk_calc_vert_uuid(uuidwalk, l_iter->v); + *val_p = (void *)uuid; + } + + /* fill faces_step_next */ + if (l_iter->radial_next != l_iter) { + BMLoop *l_iter_radial = l_iter->radial_next; + do { + if (!BLI_ghash_haskey(uuidwalk->faces_uuid, l_iter_radial->f) && + !BLI_gset_haskey(faces_step_next, l_iter_radial->f) && + (bm_uuidwalk_face_test(uuidwalk, l_iter_radial->f))) { + BLI_gset_insert(faces_step_next, l_iter_radial->f); + + /* add to fstep */ + BLI_linklist_prepend_pool(&fstep->faces, l_iter_radial->f, uuidwalk->link_pool); + } + } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter); + } + } while ((l_iter = l_iter->next) != l_first); + } + + /* faces_uuid.update(verts_new) */ + GHASH_ITER (gh_iter, verts_uuid_pass) { + BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + void *uuid_p = BLI_ghashIterator_getValue(&gh_iter); + BLI_ghash_insert(uuidwalk->verts_uuid, v, uuid_p); + } + + /* rehash faces now all their verts have been added */ + bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, false); + + uuidwalk->pass += 1; + + BLI_ghash_clear(uuidwalk->cache.verts_uuid, NULL, NULL); + BLI_gset_clear(uuidwalk->cache.faces_step, NULL); } static int bm_face_len_cmp(const void *v1, const void *v2) { - const BMFace *f1 = v1, *f2 = v2; - - if (f1->len > f2->len) { return 1; } - else if (f1->len < f2->len) { return -1; } - else { return 0; } + const BMFace *f1 = v1, *f2 = v2; + + if (f1->len > f2->len) { + return 1; + } + else if (f1->len < f2->len) { + return -1; + } + else { + return 0; + } } -static uint bm_uuidwalk_init_from_edge( - UUIDWalk *uuidwalk, BMEdge *e) +static uint bm_uuidwalk_init_from_edge(UUIDWalk *uuidwalk, BMEdge *e) { - BMLoop *l_iter = e->l; - uint f_arr_len = (uint)BM_edge_face_count(e); - BMFace **f_arr = BLI_array_alloca(f_arr, f_arr_len); - uint fstep_num = 0, i = 0; - - do { - BMFace *f = l_iter->f; - if (bm_uuidwalk_face_test(uuidwalk, f)) { - f_arr[i++] = f; - } - } while ((l_iter = l_iter->radial_next) != e->l); - BLI_assert(i <= f_arr_len); - f_arr_len = i; - - qsort(f_arr, f_arr_len, sizeof(*f_arr), bm_face_len_cmp); - - /* start us off! */ - { - const UUID_Int uuid = PRIME_VERT_INIT; - BLI_ghash_insert(uuidwalk->verts_uuid, e->v1, (void *)uuid); - BLI_ghash_insert(uuidwalk->verts_uuid, e->v2, (void *)uuid); - } - - /* turning an array into LinkNode's seems odd, - * but this is just for initialization, - * elsewhere using LinkNode's makes more sense */ - for (i = 0; i < f_arr_len; ) { - LinkNode *faces_pass = NULL; - const uint i_init = i; - const int f_len = f_arr[i]->len; - - do { - BLI_linklist_prepend_pool(&faces_pass, f_arr[i++], uuidwalk->link_pool); - } while (i < f_arr_len && (f_len == f_arr[i]->len)); - - bm_uuidwalk_pass_add(uuidwalk, faces_pass, i - i_init); - BLI_linklist_free_pool(faces_pass, NULL, uuidwalk->link_pool); - fstep_num += 1; - } - - return fstep_num; + BMLoop *l_iter = e->l; + uint f_arr_len = (uint)BM_edge_face_count(e); + BMFace **f_arr = BLI_array_alloca(f_arr, f_arr_len); + uint fstep_num = 0, i = 0; + + do { + BMFace *f = l_iter->f; + if (bm_uuidwalk_face_test(uuidwalk, f)) { + f_arr[i++] = f; + } + } while ((l_iter = l_iter->radial_next) != e->l); + BLI_assert(i <= f_arr_len); + f_arr_len = i; + + qsort(f_arr, f_arr_len, sizeof(*f_arr), bm_face_len_cmp); + + /* start us off! */ + { + const UUID_Int uuid = PRIME_VERT_INIT; + BLI_ghash_insert(uuidwalk->verts_uuid, e->v1, (void *)uuid); + BLI_ghash_insert(uuidwalk->verts_uuid, e->v2, (void *)uuid); + } + + /* turning an array into LinkNode's seems odd, + * but this is just for initialization, + * elsewhere using LinkNode's makes more sense */ + for (i = 0; i < f_arr_len;) { + LinkNode *faces_pass = NULL; + const uint i_init = i; + const int f_len = f_arr[i]->len; + + do { + BLI_linklist_prepend_pool(&faces_pass, f_arr[i++], uuidwalk->link_pool); + } while (i < f_arr_len && (f_len == f_arr[i]->len)); + + bm_uuidwalk_pass_add(uuidwalk, faces_pass, i - i_init); + BLI_linklist_free_pool(faces_pass, NULL, uuidwalk->link_pool); + fstep_num += 1; + } + + return fstep_num; } #undef PRIME_VERT_INIT /** \} */ - /** \name Internal UUIDFaceStep API * \{ */ static int facestep_sort(const void *a, const void *b) { - const UUIDFaceStepItem *fstep_a = a; - const UUIDFaceStepItem *fstep_b = b; - return (fstep_a->uuid > fstep_b->uuid) ? 1 : 0; + const UUIDFaceStepItem *fstep_a = a; + const UUIDFaceStepItem *fstep_b = b; + return (fstep_a->uuid > fstep_b->uuid) ? 1 : 0; } /** * Put faces in lists based on their uuid's, * re-run for each pass since rehashing may differentiate face-groups. */ -static bool bm_uuidwalk_facestep_begin( - UUIDWalk *uuidwalk, UUIDFaceStep *fstep) +static bool bm_uuidwalk_facestep_begin(UUIDWalk *uuidwalk, UUIDFaceStep *fstep) { - LinkNode *f_link, *f_link_next, **f_link_prev_p; - bool ok = false; - - BLI_assert(BLI_ghash_len(uuidwalk->cache.faces_from_uuid) == 0); - BLI_assert(BLI_listbase_is_empty(&fstep->items)); - - f_link_prev_p = &fstep->faces; - for (f_link = fstep->faces; f_link; f_link = f_link_next) { - BMFace *f = f_link->link; - f_link_next = f_link->next; - - /* possible another pass added this face already, free in that case */ - if (!BLI_ghash_haskey(uuidwalk->faces_uuid, f)) { - const UUID_Int uuid = bm_uuidwalk_calc_face_uuid(uuidwalk, f); - UUIDFaceStepItem *fstep_item; - void **val_p; - - ok = true; - - if (BLI_ghash_ensure_p(uuidwalk->cache.faces_from_uuid, (void *)uuid, &val_p)) { - fstep_item = *val_p; - } - else { - fstep_item = *val_p = BLI_mempool_alloc(uuidwalk->step_pool_items); - - /* add to start, so its handled on the next round of passes */ - BLI_addhead(&fstep->items, fstep_item); - fstep_item->uuid = uuid; - fstep_item->list = NULL; - fstep_item->list_len = 0; - } - - BLI_linklist_prepend_pool(&fstep_item->list, f, uuidwalk->link_pool); - fstep_item->list_len += 1; - - f_link_prev_p = &f_link->next; - } - else { - *f_link_prev_p = f_link->next; - BLI_mempool_free(uuidwalk->link_pool, f_link); - } - } - - BLI_ghash_clear(uuidwalk->cache.faces_from_uuid, NULL, NULL); - - BLI_listbase_sort(&fstep->items, facestep_sort); - - return ok; + LinkNode *f_link, *f_link_next, **f_link_prev_p; + bool ok = false; + + BLI_assert(BLI_ghash_len(uuidwalk->cache.faces_from_uuid) == 0); + BLI_assert(BLI_listbase_is_empty(&fstep->items)); + + f_link_prev_p = &fstep->faces; + for (f_link = fstep->faces; f_link; f_link = f_link_next) { + BMFace *f = f_link->link; + f_link_next = f_link->next; + + /* possible another pass added this face already, free in that case */ + if (!BLI_ghash_haskey(uuidwalk->faces_uuid, f)) { + const UUID_Int uuid = bm_uuidwalk_calc_face_uuid(uuidwalk, f); + UUIDFaceStepItem *fstep_item; + void **val_p; + + ok = true; + + if (BLI_ghash_ensure_p(uuidwalk->cache.faces_from_uuid, (void *)uuid, &val_p)) { + fstep_item = *val_p; + } + else { + fstep_item = *val_p = BLI_mempool_alloc(uuidwalk->step_pool_items); + + /* add to start, so its handled on the next round of passes */ + BLI_addhead(&fstep->items, fstep_item); + fstep_item->uuid = uuid; + fstep_item->list = NULL; + fstep_item->list_len = 0; + } + + BLI_linklist_prepend_pool(&fstep_item->list, f, uuidwalk->link_pool); + fstep_item->list_len += 1; + + f_link_prev_p = &f_link->next; + } + else { + *f_link_prev_p = f_link->next; + BLI_mempool_free(uuidwalk->link_pool, f_link); + } + } + + BLI_ghash_clear(uuidwalk->cache.faces_from_uuid, NULL, NULL); + + BLI_listbase_sort(&fstep->items, facestep_sort); + + return ok; } /** * Cleans up temp data from #bm_uuidwalk_facestep_begin */ -static void bm_uuidwalk_facestep_end( - UUIDWalk *uuidwalk, UUIDFaceStep *fstep) +static void bm_uuidwalk_facestep_end(UUIDWalk *uuidwalk, UUIDFaceStep *fstep) { - UUIDFaceStepItem *fstep_item; + UUIDFaceStepItem *fstep_item; - while ((fstep_item = BLI_pophead(&fstep->items))) { - BLI_mempool_free(uuidwalk->step_pool_items, fstep_item); - } + while ((fstep_item = BLI_pophead(&fstep->items))) { + BLI_mempool_free(uuidwalk->step_pool_items, fstep_item); + } } -static void bm_uuidwalk_facestep_free( - UUIDWalk *uuidwalk, UUIDFaceStep *fstep) +static void bm_uuidwalk_facestep_free(UUIDWalk *uuidwalk, UUIDFaceStep *fstep) { - LinkNode *f_link, *f_link_next; + LinkNode *f_link, *f_link_next; - BLI_assert(BLI_listbase_is_empty(&fstep->items)); + BLI_assert(BLI_listbase_is_empty(&fstep->items)); - for (f_link = fstep->faces; f_link; f_link = f_link_next) { - f_link_next = f_link->next; - BLI_mempool_free(uuidwalk->link_pool, f_link); - } + for (f_link = fstep->faces; f_link; f_link = f_link_next) { + f_link_next = f_link->next; + BLI_mempool_free(uuidwalk->link_pool, f_link); + } - BLI_remlink(&uuidwalk->faces_step, fstep); - BLI_mempool_free(uuidwalk->step_pool, fstep); + BLI_remlink(&uuidwalk->faces_step, fstep); + BLI_mempool_free(uuidwalk->step_pool, fstep); } /** \} */ - /* -------------------------------------------------------------------- */ /* Main Loop to match up regions */ @@ -743,197 +727,191 @@ static void bm_uuidwalk_facestep_free( */ static BMFace **bm_mesh_region_match_pair( #ifdef USE_WALKER_REUSE - UUIDWalk *w_src, UUIDWalk *w_dst, + UUIDWalk *w_src, + UUIDWalk *w_dst, #endif - BMEdge *e_src, BMEdge *e_dst, - const uint faces_src_region_len, - const uint verts_src_region_len, - uint *r_faces_result_len) + BMEdge *e_src, + BMEdge *e_dst, + const uint faces_src_region_len, + const uint verts_src_region_len, + uint *r_faces_result_len) { #ifndef USE_WALKER_REUSE - UUIDWalk w_src_, w_dst_; - UUIDWalk *w_src = &w_src_, *w_dst = &w_dst_; + UUIDWalk w_src_, w_dst_; + UUIDWalk *w_src = &w_src_, *w_dst = &w_dst_; #endif - BMFace **faces_result = NULL; - bool found = false; + BMFace **faces_result = NULL; + bool found = false; - BLI_assert(e_src != e_dst); + BLI_assert(e_src != e_dst); #ifndef USE_WALKER_REUSE - bm_uuidwalk_init(w_src, faces_src_region_len, verts_src_region_len); - bm_uuidwalk_init(w_dst, faces_src_region_len, verts_src_region_len); + bm_uuidwalk_init(w_src, faces_src_region_len, verts_src_region_len); + bm_uuidwalk_init(w_dst, faces_src_region_len, verts_src_region_len); #endif - w_src->use_face_isolate = true; - - /* setup the initial state */ - if (UNLIKELY(bm_uuidwalk_init_from_edge(w_src, e_src) != - bm_uuidwalk_init_from_edge(w_dst, e_dst))) - { - /* should never happen, if verts passed are compatible, but to be safe... */ - goto finally; - } - - bm_uuidwalk_rehash_reserve(w_src, MAX2(faces_src_region_len, verts_src_region_len)); - bm_uuidwalk_rehash_reserve(w_dst, MAX2(faces_src_region_len, verts_src_region_len)); - - while (true) { - bool ok = false; - - UUIDFaceStep *fstep_src = w_src->faces_step.first; - UUIDFaceStep *fstep_dst = w_dst->faces_step.first; - - BLI_assert(BLI_listbase_count(&w_src->faces_step) == BLI_listbase_count(&w_dst->faces_step)); - - while (fstep_src) { - - /* even if the destination has faces, - * it's not important, since the source doesn't, free and move-on. */ - if (fstep_src->faces == NULL) { - UUIDFaceStep *fstep_src_next = fstep_src->next; - UUIDFaceStep *fstep_dst_next = fstep_dst->next; - bm_uuidwalk_facestep_free(w_src, fstep_src); - bm_uuidwalk_facestep_free(w_dst, fstep_dst); - fstep_src = fstep_src_next; - fstep_dst = fstep_dst_next; - continue; - } - - if (bm_uuidwalk_facestep_begin(w_src, fstep_src) && - bm_uuidwalk_facestep_begin(w_dst, fstep_dst)) - { - /* Step over face-lists with matching UUID's - * both lists are sorted, so no need for lookups. - * The data is created on 'begin' and cleared on 'end' */ - UUIDFaceStepItem *fstep_item_src; - UUIDFaceStepItem *fstep_item_dst; - for (fstep_item_src = fstep_src->items.first, - fstep_item_dst = fstep_dst->items.first; - fstep_item_src && fstep_item_dst; - fstep_item_src = fstep_item_src->next, - fstep_item_dst = fstep_item_dst->next) - { - while ((fstep_item_dst != NULL) && - (fstep_item_dst->uuid < fstep_item_src->uuid)) - { - fstep_item_dst = fstep_item_dst->next; - } - - if ((fstep_item_dst == NULL) || - (fstep_item_src->uuid != fstep_item_dst->uuid) || - (fstep_item_src->list_len > fstep_item_dst->list_len)) - { - /* if the target walker has less than the source - * then the islands don't match, bail early */ - ok = false; - break; - } - - if (fstep_item_src->list_len == fstep_item_dst->list_len) { - /* found a match */ - bm_uuidwalk_pass_add(w_src, fstep_item_src->list, fstep_item_src->list_len); - bm_uuidwalk_pass_add(w_dst, fstep_item_dst->list, fstep_item_dst->list_len); - - BLI_linklist_free_pool(fstep_item_src->list, NULL, w_src->link_pool); - BLI_linklist_free_pool(fstep_item_dst->list, NULL, w_dst->link_pool); - - fstep_item_src->list = NULL; - fstep_item_src->list_len = 0; - - fstep_item_dst->list = NULL; - fstep_item_dst->list_len = 0; - - ok = true; - } - } - } - - bm_uuidwalk_facestep_end(w_src, fstep_src); - bm_uuidwalk_facestep_end(w_dst, fstep_dst); - - /* lock-step */ - fstep_src = fstep_src->next; - fstep_dst = fstep_dst->next; - } - - if (!ok) { - break; - } - - found = (BLI_ghash_len(w_dst->faces_uuid) == faces_src_region_len); - if (found) { - break; - } - - /* Expensive! but some cases fails without. - * (also faster in other cases since it can rule-out invalid regions) */ - bm_uuidwalk_rehash(w_src); - bm_uuidwalk_rehash(w_dst); - } - - if (found) { - GHashIterator gh_iter; - const uint faces_result_len = BLI_ghash_len(w_dst->faces_uuid); - uint i; - - faces_result = MEM_mallocN(sizeof(*faces_result) * (faces_result_len + 1), __func__); - GHASH_ITER_INDEX (gh_iter, w_dst->faces_uuid, i) { - BMFace *f = BLI_ghashIterator_getKey(&gh_iter); - faces_result[i] = f; - } - faces_result[faces_result_len] = NULL; - *r_faces_result_len = faces_result_len; - } - else { - *r_faces_result_len = 0; - } + w_src->use_face_isolate = true; + + /* setup the initial state */ + if (UNLIKELY(bm_uuidwalk_init_from_edge(w_src, e_src) != + bm_uuidwalk_init_from_edge(w_dst, e_dst))) { + /* should never happen, if verts passed are compatible, but to be safe... */ + goto finally; + } + + bm_uuidwalk_rehash_reserve(w_src, MAX2(faces_src_region_len, verts_src_region_len)); + bm_uuidwalk_rehash_reserve(w_dst, MAX2(faces_src_region_len, verts_src_region_len)); + + while (true) { + bool ok = false; + + UUIDFaceStep *fstep_src = w_src->faces_step.first; + UUIDFaceStep *fstep_dst = w_dst->faces_step.first; + + BLI_assert(BLI_listbase_count(&w_src->faces_step) == BLI_listbase_count(&w_dst->faces_step)); + + while (fstep_src) { + + /* even if the destination has faces, + * it's not important, since the source doesn't, free and move-on. */ + if (fstep_src->faces == NULL) { + UUIDFaceStep *fstep_src_next = fstep_src->next; + UUIDFaceStep *fstep_dst_next = fstep_dst->next; + bm_uuidwalk_facestep_free(w_src, fstep_src); + bm_uuidwalk_facestep_free(w_dst, fstep_dst); + fstep_src = fstep_src_next; + fstep_dst = fstep_dst_next; + continue; + } + + if (bm_uuidwalk_facestep_begin(w_src, fstep_src) && + bm_uuidwalk_facestep_begin(w_dst, fstep_dst)) { + /* Step over face-lists with matching UUID's + * both lists are sorted, so no need for lookups. + * The data is created on 'begin' and cleared on 'end' */ + UUIDFaceStepItem *fstep_item_src; + UUIDFaceStepItem *fstep_item_dst; + for (fstep_item_src = fstep_src->items.first, fstep_item_dst = fstep_dst->items.first; + fstep_item_src && fstep_item_dst; + fstep_item_src = fstep_item_src->next, fstep_item_dst = fstep_item_dst->next) { + while ((fstep_item_dst != NULL) && (fstep_item_dst->uuid < fstep_item_src->uuid)) { + fstep_item_dst = fstep_item_dst->next; + } + + if ((fstep_item_dst == NULL) || (fstep_item_src->uuid != fstep_item_dst->uuid) || + (fstep_item_src->list_len > fstep_item_dst->list_len)) { + /* if the target walker has less than the source + * then the islands don't match, bail early */ + ok = false; + break; + } + + if (fstep_item_src->list_len == fstep_item_dst->list_len) { + /* found a match */ + bm_uuidwalk_pass_add(w_src, fstep_item_src->list, fstep_item_src->list_len); + bm_uuidwalk_pass_add(w_dst, fstep_item_dst->list, fstep_item_dst->list_len); + + BLI_linklist_free_pool(fstep_item_src->list, NULL, w_src->link_pool); + BLI_linklist_free_pool(fstep_item_dst->list, NULL, w_dst->link_pool); + + fstep_item_src->list = NULL; + fstep_item_src->list_len = 0; + + fstep_item_dst->list = NULL; + fstep_item_dst->list_len = 0; + + ok = true; + } + } + } + + bm_uuidwalk_facestep_end(w_src, fstep_src); + bm_uuidwalk_facestep_end(w_dst, fstep_dst); + + /* lock-step */ + fstep_src = fstep_src->next; + fstep_dst = fstep_dst->next; + } + + if (!ok) { + break; + } + + found = (BLI_ghash_len(w_dst->faces_uuid) == faces_src_region_len); + if (found) { + break; + } + + /* Expensive! but some cases fails without. + * (also faster in other cases since it can rule-out invalid regions) */ + bm_uuidwalk_rehash(w_src); + bm_uuidwalk_rehash(w_dst); + } + + if (found) { + GHashIterator gh_iter; + const uint faces_result_len = BLI_ghash_len(w_dst->faces_uuid); + uint i; + + faces_result = MEM_mallocN(sizeof(*faces_result) * (faces_result_len + 1), __func__); + GHASH_ITER_INDEX(gh_iter, w_dst->faces_uuid, i) + { + BMFace *f = BLI_ghashIterator_getKey(&gh_iter); + faces_result[i] = f; + } + faces_result[faces_result_len] = NULL; + *r_faces_result_len = faces_result_len; + } + else { + *r_faces_result_len = 0; + } finally: #ifdef USE_WALKER_REUSE - bm_uuidwalk_clear(w_src); - bm_uuidwalk_clear(w_dst); + bm_uuidwalk_clear(w_src); + bm_uuidwalk_clear(w_dst); #else - bm_uuidwalk_free(w_src); - bm_uuidwalk_free(w_dst); + bm_uuidwalk_free(w_src); + bm_uuidwalk_free(w_dst); #endif - return faces_result; + return faces_result; } /** * Tag as visited, avoid re-use. */ -static void bm_face_array_visit( - BMFace **faces, const uint faces_len, - uint *r_verts_len, - bool visit_faces) +static void bm_face_array_visit(BMFace **faces, + const uint faces_len, + uint *r_verts_len, + bool visit_faces) { - uint verts_len = 0; - uint i; - for (i = 0; i < faces_len; i++) { - BMFace *f = faces[i]; - BMLoop *l_iter, *l_first; - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - if (r_verts_len) { - if (!BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) { - verts_len += 1; - } - } - - BM_elem_flag_enable(l_iter->e, BM_ELEM_TAG); - BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG); - } while ((l_iter = l_iter->next) != l_first); - - if (visit_faces) { - BM_elem_flag_enable(f, BM_ELEM_TAG); - } - } - - if (r_verts_len) { - *r_verts_len = verts_len; - } + uint verts_len = 0; + uint i; + for (i = 0; i < faces_len; i++) { + BMFace *f = faces[i]; + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + if (r_verts_len) { + if (!BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) { + verts_len += 1; + } + } + + BM_elem_flag_enable(l_iter->e, BM_ELEM_TAG); + BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG); + } while ((l_iter = l_iter->next) != l_first); + + if (visit_faces) { + BM_elem_flag_enable(f, BM_ELEM_TAG); + } + } + + if (r_verts_len) { + *r_verts_len = verts_len; + } } #ifdef USE_PIVOT_SEARCH @@ -946,74 +924,73 @@ typedef intptr_t SUID_Int; static bool bm_edge_is_region_boundary(BMEdge *e) { - if (e->l->radial_next != e->l) { - BMLoop *l_iter = e->l; - do { - if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { - return true; - } - } while ((l_iter = l_iter->radial_next) != e->l); - return false; - } - else { - /* boundary */ - return true; - } + if (e->l->radial_next != e->l) { + BMLoop *l_iter = e->l; + do { + if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { + return true; + } + } while ((l_iter = l_iter->radial_next) != e->l); + return false; + } + else { + /* boundary */ + return true; + } } -static void bm_face_region_pivot_edge_use_best( - GHash *gh, BMEdge *e_test, - BMEdge **r_e_pivot_best, - SUID_Int e_pivot_best_id[2]) +static void bm_face_region_pivot_edge_use_best(GHash *gh, + BMEdge *e_test, + BMEdge **r_e_pivot_best, + SUID_Int e_pivot_best_id[2]) { - SUID_Int e_pivot_test_id[2]; - - e_pivot_test_id[0] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v1); - e_pivot_test_id[1] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v2); - if (e_pivot_test_id[0] > e_pivot_test_id[1]) { - SWAP(SUID_Int, e_pivot_test_id[0], e_pivot_test_id[1]); - } - - if ((*r_e_pivot_best == NULL) || - ((e_pivot_best_id[0] != e_pivot_test_id[0]) ? - (e_pivot_best_id[0] < e_pivot_test_id[0]) : - (e_pivot_best_id[1] < e_pivot_test_id[1]))) - { - e_pivot_best_id[0] = e_pivot_test_id[0]; - e_pivot_best_id[1] = e_pivot_test_id[1]; - - /* both verts are from the same pass, record this! */ - *r_e_pivot_best = e_test; - } + SUID_Int e_pivot_test_id[2]; + + e_pivot_test_id[0] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v1); + e_pivot_test_id[1] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v2); + if (e_pivot_test_id[0] > e_pivot_test_id[1]) { + SWAP(SUID_Int, e_pivot_test_id[0], e_pivot_test_id[1]); + } + + if ((*r_e_pivot_best == NULL) || + ((e_pivot_best_id[0] != e_pivot_test_id[0]) ? (e_pivot_best_id[0] < e_pivot_test_id[0]) : + (e_pivot_best_id[1] < e_pivot_test_id[1]))) { + e_pivot_best_id[0] = e_pivot_test_id[0]; + e_pivot_best_id[1] = e_pivot_test_id[1]; + + /* both verts are from the same pass, record this! */ + *r_e_pivot_best = e_test; + } } /* quick id from a boundary vertex */ static SUID_Int bm_face_region_vert_boundary_id(BMVert *v) { -#define PRIME_VERT_SMALL_A 7 -#define PRIME_VERT_SMALL_B 13 -#define PRIME_VERT_MID_A 103 -#define PRIME_VERT_MID_B 131 - - int tot = 0; - BMIter iter; - BMLoop *l; - SUID_Int id = PRIME_VERT_MID_A; - - BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { - const bool is_boundary_vert = (bm_edge_is_region_boundary(l->e) || bm_edge_is_region_boundary(l->prev->e)); - id ^= l->f->len * (is_boundary_vert ? PRIME_VERT_SMALL_A : PRIME_VERT_SMALL_B); - tot += 1; - } - - id ^= (tot * PRIME_VERT_MID_B); - - return id ? ABS(id) : 1; - -#undef PRIME_VERT_SMALL_A -#undef PRIME_VERT_SMALL_B -#undef PRIME_VERT_MID_A -#undef PRIME_VERT_MID_B +# define PRIME_VERT_SMALL_A 7 +# define PRIME_VERT_SMALL_B 13 +# define PRIME_VERT_MID_A 103 +# define PRIME_VERT_MID_B 131 + + int tot = 0; + BMIter iter; + BMLoop *l; + SUID_Int id = PRIME_VERT_MID_A; + + BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { + const bool is_boundary_vert = (bm_edge_is_region_boundary(l->e) || + bm_edge_is_region_boundary(l->prev->e)); + id ^= l->f->len * (is_boundary_vert ? PRIME_VERT_SMALL_A : PRIME_VERT_SMALL_B); + tot += 1; + } + + id ^= (tot * PRIME_VERT_MID_B); + + return id ? ABS(id) : 1; + +# undef PRIME_VERT_SMALL_A +# undef PRIME_VERT_SMALL_B +# undef PRIME_VERT_MID_A +# undef PRIME_VERT_MID_B } /** @@ -1021,52 +998,52 @@ static SUID_Int bm_face_region_vert_boundary_id(BMVert *v) */ static SUID_Int bm_face_region_vert_pass_id(GHash *gh, BMVert *v) { - BMIter eiter; - BMEdge *e; - SUID_Int tot = 0; - SUID_Int v_sum_face_len = 0; - SUID_Int v_sum_id = 0; - SUID_Int id; - SUID_Int id_min = INTPTR_MIN + 1; - -#define PRIME_VERT_MID_A 23 -#define PRIME_VERT_MID_B 31 - - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - BMVert *v_other = BM_edge_other_vert(e, v); - if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { - /* non-zero values aren't allowed... so no need to check haskey */ - SUID_Int v_other_id = (SUID_Int)BLI_ghash_lookup(gh, v_other); - if (v_other_id > 0) { - v_sum_id += v_other_id; - tot += 1; - - /* face-count */ - { - BMLoop *l_iter = e->l; - do { - if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { - v_sum_face_len += l_iter->f->len; - } - } while ((l_iter = l_iter->radial_next) != e->l); - } - } - } - } - } - - id = (tot * PRIME_VERT_MID_A); - id ^= (v_sum_face_len * PRIME_VERT_MID_B); - id ^= v_sum_id; - - /* disallow 0 & min (since it can't be flipped) */ - id = (UNLIKELY(id == 0) ? 1 : UNLIKELY(id < id_min) ? id_min : id); - - return ABS(id); - -#undef PRIME_VERT_MID_A -#undef PRIME_VERT_MID_B + BMIter eiter; + BMEdge *e; + SUID_Int tot = 0; + SUID_Int v_sum_face_len = 0; + SUID_Int v_sum_id = 0; + SUID_Int id; + SUID_Int id_min = INTPTR_MIN + 1; + +# define PRIME_VERT_MID_A 23 +# define PRIME_VERT_MID_B 31 + + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + /* non-zero values aren't allowed... so no need to check haskey */ + SUID_Int v_other_id = (SUID_Int)BLI_ghash_lookup(gh, v_other); + if (v_other_id > 0) { + v_sum_id += v_other_id; + tot += 1; + + /* face-count */ + { + BMLoop *l_iter = e->l; + do { + if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { + v_sum_face_len += l_iter->f->len; + } + } while ((l_iter = l_iter->radial_next) != e->l); + } + } + } + } + } + + id = (tot * PRIME_VERT_MID_A); + id ^= (v_sum_face_len * PRIME_VERT_MID_B); + id ^= v_sum_id; + + /* disallow 0 & min (since it can't be flipped) */ + id = (UNLIKELY(id == 0) ? 1 : UNLIKELY(id < id_min) ? id_min : id); + + return ABS(id); + +# undef PRIME_VERT_MID_A +# undef PRIME_VERT_MID_B } /** @@ -1076,185 +1053,184 @@ static SUID_Int bm_face_region_vert_pass_id(GHash *gh, BMVert *v) * * This is only called once on the source region (no need to be highly optimized). */ -static BMEdge *bm_face_region_pivot_edge_find( - BMFace **faces_region, uint faces_region_len, - uint verts_region_len, - uint *r_depth) +static BMEdge *bm_face_region_pivot_edge_find(BMFace **faces_region, + uint faces_region_len, + uint verts_region_len, + uint *r_depth) { - /* note, keep deterministic where possible (geometry order independent) - * this function assumed all visit faces & edges are tagged */ - - BLI_LINKSTACK_DECLARE(vert_queue_prev, BMVert *); - BLI_LINKSTACK_DECLARE(vert_queue_next, BMVert *); - - GHash *gh = BLI_ghash_ptr_new(__func__); - uint i; - - BMEdge *e_pivot = NULL; - /* pick any non-boundary edge (not ideal) */ - BMEdge *e_pivot_fallback = NULL; - - SUID_Int pass = 0; - - /* total verts in 'gs' we have visited - aka - not v_init_none */ - uint vert_queue_used = 0; - - BLI_LINKSTACK_INIT(vert_queue_prev); - BLI_LINKSTACK_INIT(vert_queue_next); - - /* face-verts */ - for (i = 0; i < faces_region_len; i++) { - BMFace *f = faces_region[i]; - - BMLoop *l_iter, *l_first; - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - BMEdge *e = l_iter->e; - if (bm_edge_is_region_boundary(e)) { - uint j; - for (j = 0; j < 2; j++) { - void **val_p; - if (!BLI_ghash_ensure_p(gh, (&e->v1)[j], &val_p)) { - SUID_Int v_id = bm_face_region_vert_boundary_id((&e->v1)[j]); - *val_p = (void *)v_id; - BLI_LINKSTACK_PUSH(vert_queue_prev, (&e->v1)[j]); - vert_queue_used += 1; - } - } - } - else { - /* use incase (depth == 0), no interior verts */ - e_pivot_fallback = e; - } - } while ((l_iter = l_iter->next) != l_first); - } - - while (BLI_LINKSTACK_SIZE(vert_queue_prev)) { - BMVert *v; - while ((v = BLI_LINKSTACK_POP(vert_queue_prev))) { - BMIter eiter; - BMEdge *e; - BLI_assert(BLI_ghash_haskey(gh, v)); - BLI_assert((SUID_Int)BLI_ghash_lookup(gh, v) > 0); - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - BMVert *v_other = BM_edge_other_vert(e, v); - if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { - void **val_p; - if (!BLI_ghash_ensure_p(gh, v_other, &val_p)) { - /* add as negative, so we know not to read from them this pass */ - const SUID_Int v_id_other = -bm_face_region_vert_pass_id(gh, v_other); - *val_p = (void *)v_id_other; - BLI_LINKSTACK_PUSH(vert_queue_next, v_other); - vert_queue_used += 1; - } - } - } - } - } - - /* flip all the newly added hashes to positive */ - { - LinkNode *v_link; - for (v_link = vert_queue_next; v_link; v_link = v_link->next) { - SUID_Int *v_id_p = (SUID_Int *)BLI_ghash_lookup_p(gh, v_link->link); - *v_id_p = -(*v_id_p); - BLI_assert(*v_id_p > 0); - } - } - - BLI_LINKSTACK_SWAP(vert_queue_prev, vert_queue_next); - pass += 1; - - if (vert_queue_used == verts_region_len) { - break; - } - } - - if (BLI_LINKSTACK_SIZE(vert_queue_prev) >= 2) { - /* common case - we managed to find some interior verts */ - LinkNode *v_link; - BMEdge *e_pivot_best = NULL; - SUID_Int e_pivot_best_id[2] = {0, 0}; - - /* temp untag, so we can quickly know what other verts are in this last pass */ - for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { - BMVert *v = v_link->link; - BM_elem_flag_disable(v, BM_ELEM_TAG); - } - - /* restore correct tagging */ - for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { - BMIter eiter; - BMEdge *e_test; - - BMVert *v = v_link->link; - BM_elem_flag_enable(v, BM_ELEM_TAG); - - BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) { - if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) { - BMVert *v_other = BM_edge_other_vert(e_test, v); - if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == false) { - bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id); - } - } - } - } - - e_pivot = e_pivot_best; - } - - if ((e_pivot == NULL) && BLI_LINKSTACK_SIZE(vert_queue_prev)) { - /* find the best single edge */ - BMEdge *e_pivot_best = NULL; - SUID_Int e_pivot_best_id[2] = {0, 0}; - - LinkNode *v_link; - - /* reduce a pass since we're having to step into a previous passes vert, - * and will be closer to the boundary */ - BLI_assert(pass != 0); - pass -= 1; - - for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { - BMVert *v = v_link->link; - - BMIter eiter; - BMEdge *e_test; - BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) { - if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) { - BMVert *v_other = BM_edge_other_vert(e_test, v); - if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { - bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id); - } - } - } - } - - e_pivot = e_pivot_best; - } - - BLI_LINKSTACK_FREE(vert_queue_prev); - BLI_LINKSTACK_FREE(vert_queue_next); - - BLI_ghash_free(gh, NULL, NULL); - - if (e_pivot == NULL) { -#ifdef DEBUG_PRINT - printf("%s: using fallback edge!\n", __func__); -#endif - e_pivot = e_pivot_fallback; - pass = 0; - } - - *r_depth = (uint)pass; - - return e_pivot; + /* note, keep deterministic where possible (geometry order independent) + * this function assumed all visit faces & edges are tagged */ + + BLI_LINKSTACK_DECLARE(vert_queue_prev, BMVert *); + BLI_LINKSTACK_DECLARE(vert_queue_next, BMVert *); + + GHash *gh = BLI_ghash_ptr_new(__func__); + uint i; + + BMEdge *e_pivot = NULL; + /* pick any non-boundary edge (not ideal) */ + BMEdge *e_pivot_fallback = NULL; + + SUID_Int pass = 0; + + /* total verts in 'gs' we have visited - aka - not v_init_none */ + uint vert_queue_used = 0; + + BLI_LINKSTACK_INIT(vert_queue_prev); + BLI_LINKSTACK_INIT(vert_queue_next); + + /* face-verts */ + for (i = 0; i < faces_region_len; i++) { + BMFace *f = faces_region[i]; + + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + BMEdge *e = l_iter->e; + if (bm_edge_is_region_boundary(e)) { + uint j; + for (j = 0; j < 2; j++) { + void **val_p; + if (!BLI_ghash_ensure_p(gh, (&e->v1)[j], &val_p)) { + SUID_Int v_id = bm_face_region_vert_boundary_id((&e->v1)[j]); + *val_p = (void *)v_id; + BLI_LINKSTACK_PUSH(vert_queue_prev, (&e->v1)[j]); + vert_queue_used += 1; + } + } + } + else { + /* use incase (depth == 0), no interior verts */ + e_pivot_fallback = e; + } + } while ((l_iter = l_iter->next) != l_first); + } + + while (BLI_LINKSTACK_SIZE(vert_queue_prev)) { + BMVert *v; + while ((v = BLI_LINKSTACK_POP(vert_queue_prev))) { + BMIter eiter; + BMEdge *e; + BLI_assert(BLI_ghash_haskey(gh, v)); + BLI_assert((SUID_Int)BLI_ghash_lookup(gh, v) > 0); + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + void **val_p; + if (!BLI_ghash_ensure_p(gh, v_other, &val_p)) { + /* add as negative, so we know not to read from them this pass */ + const SUID_Int v_id_other = -bm_face_region_vert_pass_id(gh, v_other); + *val_p = (void *)v_id_other; + BLI_LINKSTACK_PUSH(vert_queue_next, v_other); + vert_queue_used += 1; + } + } + } + } + } + + /* flip all the newly added hashes to positive */ + { + LinkNode *v_link; + for (v_link = vert_queue_next; v_link; v_link = v_link->next) { + SUID_Int *v_id_p = (SUID_Int *)BLI_ghash_lookup_p(gh, v_link->link); + *v_id_p = -(*v_id_p); + BLI_assert(*v_id_p > 0); + } + } + + BLI_LINKSTACK_SWAP(vert_queue_prev, vert_queue_next); + pass += 1; + + if (vert_queue_used == verts_region_len) { + break; + } + } + + if (BLI_LINKSTACK_SIZE(vert_queue_prev) >= 2) { + /* common case - we managed to find some interior verts */ + LinkNode *v_link; + BMEdge *e_pivot_best = NULL; + SUID_Int e_pivot_best_id[2] = {0, 0}; + + /* temp untag, so we can quickly know what other verts are in this last pass */ + for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { + BMVert *v = v_link->link; + BM_elem_flag_disable(v, BM_ELEM_TAG); + } + + /* restore correct tagging */ + for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { + BMIter eiter; + BMEdge *e_test; + + BMVert *v = v_link->link; + BM_elem_flag_enable(v, BM_ELEM_TAG); + + BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e_test, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == false) { + bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id); + } + } + } + } + + e_pivot = e_pivot_best; + } + + if ((e_pivot == NULL) && BLI_LINKSTACK_SIZE(vert_queue_prev)) { + /* find the best single edge */ + BMEdge *e_pivot_best = NULL; + SUID_Int e_pivot_best_id[2] = {0, 0}; + + LinkNode *v_link; + + /* reduce a pass since we're having to step into a previous passes vert, + * and will be closer to the boundary */ + BLI_assert(pass != 0); + pass -= 1; + + for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { + BMVert *v = v_link->link; + + BMIter eiter; + BMEdge *e_test; + BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e_test, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id); + } + } + } + } + + e_pivot = e_pivot_best; + } + + BLI_LINKSTACK_FREE(vert_queue_prev); + BLI_LINKSTACK_FREE(vert_queue_next); + + BLI_ghash_free(gh, NULL, NULL); + + if (e_pivot == NULL) { +# ifdef DEBUG_PRINT + printf("%s: using fallback edge!\n", __func__); +# endif + e_pivot = e_pivot_fallback; + pass = 0; + } + + *r_depth = (uint)pass; + + return e_pivot; } /** \} */ -#endif /* USE_PIVOT_SEARCH */ - +#endif /* USE_PIVOT_SEARCH */ /* -------------------------------------------------------------------- */ /* Quick UUID pass - identify candidates */ @@ -1268,104 +1244,96 @@ typedef uintptr_t UUIDFashMatch; static UUIDFashMatch bm_vert_fasthash_single(BMVert *v) { - BMIter eiter; - BMEdge *e; - UUIDFashMatch e_num = 0, f_num = 0, l_num = 0; - -#define PRIME_EDGE 7 -#define PRIME_FACE 31 -#define PRIME_LOOP 61 - - BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - if (!BM_edge_is_wire(e)) { - BMLoop *l_iter = e->l; - e_num += 1; - do { - f_num += 1; - l_num += (uint)l_iter->f->len; - } while ((l_iter = l_iter->radial_next) != e->l); - } - } - - return ((e_num * PRIME_EDGE) ^ - (f_num * PRIME_FACE) * - (l_num * PRIME_LOOP)); - -#undef PRIME_EDGE -#undef PRIME_FACE -#undef PRIME_LOOP + BMIter eiter; + BMEdge *e; + UUIDFashMatch e_num = 0, f_num = 0, l_num = 0; + +# define PRIME_EDGE 7 +# define PRIME_FACE 31 +# define PRIME_LOOP 61 + + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + if (!BM_edge_is_wire(e)) { + BMLoop *l_iter = e->l; + e_num += 1; + do { + f_num += 1; + l_num += (uint)l_iter->f->len; + } while ((l_iter = l_iter->radial_next) != e->l); + } + } + + return ((e_num * PRIME_EDGE) ^ (f_num * PRIME_FACE) * (l_num * PRIME_LOOP)); + +# undef PRIME_EDGE +# undef PRIME_FACE +# undef PRIME_LOOP } -static UUIDFashMatch *bm_vert_fasthash_create( - BMesh *bm, const uint depth) +static UUIDFashMatch *bm_vert_fasthash_create(BMesh *bm, const uint depth) { - UUIDFashMatch *id_prev; - UUIDFashMatch *id_curr; - uint pass, i; - BMVert *v; - BMIter iter; + UUIDFashMatch *id_prev; + UUIDFashMatch *id_curr; + uint pass, i; + BMVert *v; + BMIter iter; - id_prev = MEM_mallocN(sizeof(*id_prev) * (uint)bm->totvert, __func__); - id_curr = MEM_mallocN(sizeof(*id_curr) * (uint)bm->totvert, __func__); + id_prev = MEM_mallocN(sizeof(*id_prev) * (uint)bm->totvert, __func__); + id_curr = MEM_mallocN(sizeof(*id_curr) * (uint)bm->totvert, __func__); - BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { - id_prev[i] = bm_vert_fasthash_single(v); - } + BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { + id_prev[i] = bm_vert_fasthash_single(v); + } - for (pass = 0; pass < depth; pass++) { - BMEdge *e; + for (pass = 0; pass < depth; pass++) { + BMEdge *e; - memcpy(id_curr, id_prev, sizeof(*id_prev) * (uint)bm->totvert); + memcpy(id_curr, id_prev, sizeof(*id_prev) * (uint)bm->totvert); - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - if (BM_edge_is_wire(e) == false) { - const int i1 = BM_elem_index_get(e->v1); - const int i2 = BM_elem_index_get(e->v2); + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_edge_is_wire(e) == false) { + const int i1 = BM_elem_index_get(e->v1); + const int i2 = BM_elem_index_get(e->v2); - id_curr[i1] += id_prev[i2]; - id_curr[i2] += id_prev[i1]; - } - } - } - MEM_freeN(id_prev); + id_curr[i1] += id_prev[i2]; + id_curr[i2] += id_prev[i1]; + } + } + } + MEM_freeN(id_prev); - return id_curr; + return id_curr; } -static void bm_vert_fasthash_edge_order( - UUIDFashMatch *fm, const BMEdge *e, UUIDFashMatch e_fm[2]) +static void bm_vert_fasthash_edge_order(UUIDFashMatch *fm, const BMEdge *e, UUIDFashMatch e_fm[2]) { - e_fm[0] = fm[BM_elem_index_get(e->v1)]; - e_fm[1] = fm[BM_elem_index_get(e->v2)]; + e_fm[0] = fm[BM_elem_index_get(e->v1)]; + e_fm[1] = fm[BM_elem_index_get(e->v2)]; - if (e_fm[0] > e_fm[1]) { - SWAP(UUIDFashMatch, e_fm[0], e_fm[1]); - } + if (e_fm[0] > e_fm[1]) { + SWAP(UUIDFashMatch, e_fm[0], e_fm[1]); + } } -static bool bm_vert_fasthash_edge_is_match( - UUIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b) +static bool bm_vert_fasthash_edge_is_match(UUIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b) { - UUIDFashMatch e_a_fm[2]; - UUIDFashMatch e_b_fm[2]; + UUIDFashMatch e_a_fm[2]; + UUIDFashMatch e_b_fm[2]; - bm_vert_fasthash_edge_order(fm, e_a, e_a_fm); - bm_vert_fasthash_edge_order(fm, e_b, e_b_fm); + bm_vert_fasthash_edge_order(fm, e_a, e_a_fm); + bm_vert_fasthash_edge_order(fm, e_b, e_b_fm); - return ((e_a_fm[0] == e_b_fm[0]) && - (e_a_fm[1] == e_b_fm[1])); + return ((e_a_fm[0] == e_b_fm[0]) && (e_a_fm[1] == e_b_fm[1])); } -static void bm_vert_fasthash_destroy( - UUIDFashMatch *fm) +static void bm_vert_fasthash_destroy(UUIDFashMatch *fm) { - MEM_freeN(fm); + MEM_freeN(fm); } /** \} */ -#endif /* USE_PIVOT_FASTMATCH */ - +#endif /* USE_PIVOT_FASTMATCH */ /** * Take a face-region and return a list of matching face-regions. @@ -1373,143 +1341,142 @@ static void bm_vert_fasthash_destroy( * \param faces_region: A single, contiguous face-region. * \return A list of matching null-terminated face-region arrays. */ -int BM_mesh_region_match( - BMesh *bm, - BMFace **faces_region, uint faces_region_len, - ListBase *r_face_regions) +int BM_mesh_region_match(BMesh *bm, + BMFace **faces_region, + uint faces_region_len, + ListBase *r_face_regions) { - BMEdge *e_src; - BMEdge *e_dst; - BMIter iter; - uint verts_region_len = 0; - uint faces_result_len = 0; - /* number of steps from e_src to a boundary vert */ - uint depth; - + BMEdge *e_src; + BMEdge *e_dst; + BMIter iter; + uint verts_region_len = 0; + uint faces_result_len = 0; + /* number of steps from e_src to a boundary vert */ + uint depth; #ifdef USE_WALKER_REUSE - UUIDWalk w_src, w_dst; + UUIDWalk w_src, w_dst; #endif #ifdef USE_PIVOT_FASTMATCH - UUIDFashMatch *fm; + UUIDFashMatch *fm; #endif #ifdef DEBUG_PRINT - int search_num = 0; + int search_num = 0; #endif #ifdef DEBUG_TIME - TIMEIT_START(region_match); + TIMEIT_START(region_match); #endif - /* initialize visited verts */ - BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false); - bm_face_array_visit(faces_region, faces_region_len, &verts_region_len, true); + /* initialize visited verts */ + BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false); + bm_face_array_visit(faces_region, faces_region_len, &verts_region_len, true); - /* needed for 'ghashutil_bmelem_indexhash' */ - BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE); + /* needed for 'ghashutil_bmelem_indexhash' */ + BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE); #ifdef USE_PIVOT_SEARCH - e_src = bm_face_region_pivot_edge_find( - faces_region, faces_region_len, - verts_region_len, &depth); - - /* see which edge is added */ -#if 0 - BM_select_history_clear(bm); - if (e_src) { - BM_select_history_store(bm, e_src); - } -#endif + e_src = bm_face_region_pivot_edge_find(faces_region, faces_region_len, verts_region_len, &depth); + + /* see which edge is added */ +# if 0 + BM_select_history_clear(bm); + if (e_src) { + BM_select_history_store(bm, e_src); + } +# endif #else - /* quick test only! */ - e_src = BM_mesh_active_edge_get(bm); + /* quick test only! */ + e_src = BM_mesh_active_edge_get(bm); #endif - if (e_src == NULL) { + if (e_src == NULL) { #ifdef DEBUG_PRINT - printf("Couldn't find 'e_src'"); + printf("Couldn't find 'e_src'"); #endif - return 0; - } + return 0; + } - BLI_listbase_clear(r_face_regions); + BLI_listbase_clear(r_face_regions); #ifdef USE_PIVOT_FASTMATCH - if (depth > 0) { - fm = bm_vert_fasthash_create(bm, depth); - } - else { - fm = NULL; - } + if (depth > 0) { + fm = bm_vert_fasthash_create(bm, depth); + } + else { + fm = NULL; + } #endif #ifdef USE_WALKER_REUSE - bm_uuidwalk_init(&w_src, faces_region_len, verts_region_len); - bm_uuidwalk_init(&w_dst, faces_region_len, verts_region_len); + bm_uuidwalk_init(&w_src, faces_region_len, verts_region_len); + bm_uuidwalk_init(&w_dst, faces_region_len, verts_region_len); #endif - BM_ITER_MESH (e_dst, &iter, bm, BM_EDGES_OF_MESH) { - BMFace **faces_result; - uint faces_result_len_out; + BM_ITER_MESH (e_dst, &iter, bm, BM_EDGES_OF_MESH) { + BMFace **faces_result; + uint faces_result_len_out; - if (BM_elem_flag_test(e_dst, BM_ELEM_TAG) || BM_edge_is_wire(e_dst)) { - continue; - } + if (BM_elem_flag_test(e_dst, BM_ELEM_TAG) || BM_edge_is_wire(e_dst)) { + continue; + } #ifdef USE_PIVOT_FASTMATCH - if (fm && !bm_vert_fasthash_edge_is_match(fm, e_src, e_dst)) { - continue; - } + if (fm && !bm_vert_fasthash_edge_is_match(fm, e_src, e_dst)) { + continue; + } #endif #ifdef DEBUG_PRINT - search_num += 1; + search_num += 1; #endif - faces_result = bm_mesh_region_match_pair( + faces_result = bm_mesh_region_match_pair( #ifdef USE_WALKER_REUSE - &w_src, &w_dst, + &w_src, + &w_dst, #endif - e_src, e_dst, - faces_region_len, - verts_region_len, - &faces_result_len_out); + e_src, + e_dst, + faces_region_len, + verts_region_len, + &faces_result_len_out); - /* tag verts as visited */ - if (faces_result) { - LinkData *link; + /* tag verts as visited */ + if (faces_result) { + LinkData *link; - bm_face_array_visit(faces_result, faces_result_len_out, NULL, false); + bm_face_array_visit(faces_result, faces_result_len_out, NULL, false); - link = BLI_genericNodeN(faces_result); - BLI_addtail(r_face_regions, link); - faces_result_len += 1; - } - } + link = BLI_genericNodeN(faces_result); + BLI_addtail(r_face_regions, link); + faces_result_len += 1; + } + } #ifdef USE_WALKER_REUSE - bm_uuidwalk_free(&w_src); - bm_uuidwalk_free(&w_dst); + bm_uuidwalk_free(&w_src); + bm_uuidwalk_free(&w_dst); #else - (void)bm_uuidwalk_clear; + (void)bm_uuidwalk_clear; #endif #ifdef USE_PIVOT_FASTMATCH - if (fm) { - bm_vert_fasthash_destroy(fm); - } + if (fm) { + bm_vert_fasthash_destroy(fm); + } #endif #ifdef DEBUG_PRINT - printf("%s: search: %d, found %d\n", __func__, search_num, faces_result_len); + printf("%s: search: %d, found %d\n", __func__, search_num, faces_result_len); #endif #ifdef DEBUG_TIME - TIMEIT_END(region_match); + TIMEIT_END(region_match); #endif - return (int)faces_result_len; + return (int)faces_result_len; } |