[Bf-blender-cvs] [2f4e707] master: BMesh: select similar regions
Campbell Barton
noreply at git.blender.org
Fri Sep 26 15:20:06 CEST 2014
Commit: 2f4e70702c5bd42845f6f7353cf6c8c0acc0bea0
Author: Campbell Barton
Date: Mon Sep 15 15:40:50 2014 +1000
Branches: master
https://developer.blender.org/rB2f4e70702c5bd42845f6f7353cf6c8c0acc0bea0
BMesh: select similar regions
Select operator that takes multiple selected face regions and
selects any number of matching regions (when they have distinguishing features to isolate them).
UI access next.
===================================================================
M source/blender/bmesh/CMakeLists.txt
M source/blender/bmesh/bmesh_tools.h
A source/blender/bmesh/tools/bmesh_region_match.c
A source/blender/bmesh/tools/bmesh_region_match.h
M source/blender/editors/mesh/editmesh_select.c
M source/blender/editors/mesh/mesh_intern.h
M source/blender/editors/mesh/mesh_ops.c
===================================================================
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index a43e835..50d3ac3 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -140,6 +140,8 @@ set(SRC
tools/bmesh_intersect.h
tools/bmesh_path.c
tools/bmesh_path.h
+ tools/bmesh_region_match.c
+ tools/bmesh_region_match.h
tools/bmesh_triangulate.c
tools/bmesh_triangulate.h
tools/bmesh_wireframe.c
diff --git a/source/blender/bmesh/bmesh_tools.h b/source/blender/bmesh/bmesh_tools.h
index baffeb7..f7f767f 100644
--- a/source/blender/bmesh/bmesh_tools.h
+++ b/source/blender/bmesh/bmesh_tools.h
@@ -41,6 +41,7 @@ extern "C" {
#include "tools/bmesh_edgenet.h"
#include "tools/bmesh_edgesplit.h"
#include "tools/bmesh_path.h"
+#include "tools/bmesh_region_match.h"
#include "tools/bmesh_triangulate.h"
#ifdef __cplusplus
diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c
new file mode 100644
index 0000000..26c3271
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_region_match.c
@@ -0,0 +1,1501 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/tools/bmesh_region_match.c
+ * \ingroup bmesh
+ *
+ * Given a contiguous region of faces,
+ * find multiple matching regions (based on topology) and return them.
+ */
+
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+#include "BLI_listbase.h"
+#include "BLI_linklist.h"
+#include "BLI_alloca.h"
+#include "BLI_ghash.h"
+#include "BLI_mempool.h"
+#include "BLI_linklist_stack.h"
+
+#include "bmesh.h"
+
+#include "tools/bmesh_region_match.h" /* own incldue */
+
+/* avoid re-creating ghash and pools for each search */
+#define USE_WALKER_REUSE
+
+/* do a first-pass id of all vertices,
+ * this avoids expensive checks on every item later on
+ * (works fine without, just slower) */
+#define USE_PIVOT_FASTMATCH
+
+/* otherwise use active element as pivot, for quick tests only */
+#define USE_PIVOT_SEARCH
+
+// #define DEBUG_TIME
+// #define DEBUG_PRINT
+
+#ifdef DEBUG_TIME
+# include "PIL_time.h"
+# include "PIL_time_utildefines.h"
+#endif
+
+#include "BLI_strict_flags.h"
+
+
+/* -------------------------------------------------------------------- */
+/* UUID-Walk API */
+
+/** \name Internal UUIDWalk API
+ * \{ */
+
+#define PRIME_VERT_INIT 100003
+
+typedef uintptr_t UUID_Int;
+
+typedef struct UUIDWalk {
+
+ /* List of faces we can step onto (UUIDFaceStep's) */
+ ListBase faces_step;
+
+ /* Face & Vert UUID's */
+ GHash *verts_uuid;
+ GHash *faces_uuid;
+
+ /* memory pool for LinkNode's */
+ BLI_mempool *link_pool;
+
+ /* memory pool for LinkBase's */
+ BLI_mempool *lbase_pool;
+
+ /* 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;
+
+ /* 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 */
+
+ GHash *faces_from_uuid; /* UUID -> UUIDFaceStepItem */
+
+ UUID_Int *rehash_store;
+ unsigned int rehash_store_len;
+ } cache;
+
+} UUIDWalk;
+
+/* stores a set of potential faces to step onto */
+typedef struct UUIDFaceStep {
+ struct UUIDFaceStep *next, *prev;
+
+ /* unsorted 'BMFace' */
+ LinkNode *faces;
+
+ /* faces sorted into 'UUIDFaceStepItem' */
+ ListBase items;
+} UUIDFaceStep;
+
+/* store face-lists with same uuid */
+typedef struct UUIDFaceStepItem {
+ struct UUIDFaceStepItem *next, *prev;
+ uintptr_t uuid;
+
+ LinkNode *list;
+ unsigned int list_len;
+} UUIDFaceStepItem;
+
+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;
+ }
+}
+
+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;
+ }
+}
+
+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;
+ }
+}
+
+static unsigned int ghashutil_bmelem_indexhash(const void *key)
+{
+ const BMElem *ele = key;
+ return (unsigned int)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);
+}
+
+static GHash *ghash_bmelem_new_ex(const char *info,
+ const unsigned int 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 unsigned int 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);
+}
+
+static GSet *gset_bmelem_new(const char *info)
+{
+ return gset_bmelem_new_ex(info, 0);
+}
+
+
+static void bm_uuidwalk_init(
+ UUIDWalk *uuidwalk,
+ const unsigned int faces_src_region_len,
+ const unsigned int verts_src_region_len)
+{
+ 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->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__);
+
+ uuidwalk->cache.rehash_store = NULL;
+ uuidwalk->cache.rehash_store_len = 0;
+
+ 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);
+
+ uuidwalk->pass = 1;
+}
+
+static void bm_uuidwalk_clear(
+ UUIDWalk *uuidwalk)
+{
+ 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->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 */
+
+ uuidwalk->use_face_isolate = false;
+
+ BLI_mempool_clear(uuidwalk->link_pool);
+ BLI_mempool_clear(uuidwalk->step_pool);
+ BLI_mempool_clear(uuidwalk->step_pool_items);
+
+ uuidwalk->pass = 1;
+}
+
+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);
+}
+
+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 */
+ {
+ unsigned int 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 */
+ {
+ unsigned int 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
+#undef PRIME_VERT_LARGE
+
+#undef PRIME_FACE_SMALL
+#undef PRIME_FACE_MID
+}
+
+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 * (unsigned int)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 (
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list