Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCampbell Barton <ideasman42@gmail.com>2019-04-17 07:17:24 +0300
committerCampbell Barton <ideasman42@gmail.com>2019-04-17 07:21:24 +0300
commite12c08e8d170b7ca40f204a5b0423c23a9fbc2c1 (patch)
tree8cf3453d12edb177a218ef8009357518ec6cab6a /source/blender/bmesh/tools/bmesh_region_match.c
parentb3dabc200a4b0399ec6b81f2ff2730d07b44fcaa (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.c2183
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;
}