[Bf-blender-cvs] [85b4c61] soc-2014-shapekey: Reorganization and better topohash code (2 times faster at least).
Bastien Montagne
noreply at git.blender.org
Fri Nov 14 13:02:18 CET 2014
Commit: 85b4c61b4e41c8931ce0b4179e6c4e170f6eadaf
Author: Bastien Montagne
Date: Tue Nov 11 17:27:19 2014 +0100
Branches: soc-2014-shapekey
https://developer.blender.org/rB85b4c61b4e41c8931ce0b4179e6c4e170f6eadaf
Reorganization and better topohash code (2 times faster at least).
WIP, will move murmur2a to BLI in master first.
===================================================================
M source/blender/blenkernel/intern/editmesh.c
M source/blender/bmesh/intern/bmesh_queries.c
M source/blender/bmesh/intern/bmesh_queries.h
===================================================================
diff --git a/source/blender/blenkernel/intern/editmesh.c b/source/blender/blenkernel/intern/editmesh.c
index 445aa4e..5aad2f7 100644
--- a/source/blender/blenkernel/intern/editmesh.c
+++ b/source/blender/blenkernel/intern/editmesh.c
@@ -250,110 +250,21 @@ void BKE_editmesh_color_ensure(BMEditMesh *em, const char htype)
/* ==================== topology hashing ======================= */
- static unsigned int mm2_hash(char *key, unsigned int len, unsigned int seed) {
- const unsigned int m = 0x5bd1e995;
- char r = 24;
- unsigned int h = len + seed;
- for (; len >= 4; len -= 4, key += 4) {
- unsigned int k = *(unsigned int *) key * m;
- k ^= k >> r;
- k *= m;
- h = (h * m) ^ k;
- }
-
- switch (len) {
- /* everything fall-through */
- case 3:
- h ^= key[2] << 16;
- case 2:
- h ^= key[1] << 8;
- case 1:
- h ^= key[0];
- h *= m;
- default: /* do nothing */;
- }
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
- return h;
-}
-
-
- static int hashfunc(void *data, int len, int oldhash)
-{
- return (int) mm2_hash(data, len, oldhash);
-}
-
- static int hashloop_topo(BMLoop *l, int oldhash)
-{
- /* skip header, don't track customdata */
- return hashfunc(((char *)l) + sizeof(BMHeader), sizeof(BMLoop) - sizeof(BMHeader), oldhash);
-}
-
- static int hashedge_topo(BMEdge *bme, int oldhash)
-{
- return hashfunc(&bme->v1, sizeof(BMEdge) - sizeof(BMHeader) - sizeof(BMFlagLayer *), oldhash);
-}
-
- static int hashface_topo(BMFace *f, int oldhash)
-{
- /* skip header & flags & face normals and material */
- int a = f->len + GET_INT_FROM_POINTER(f->l_first);
- return hashfunc(&a, sizeof(int), oldhash);
-}
-
- static int bmesh_topohash(BMesh *bm)
-{
- BMIter iter;
- BMFace *f;
- BMVert *v;
-
- int hash = bm->totedge + bm->totvert + bm->totloop + bm->totface;
-
- if (!hash) {
- return 0;
- }
-
- if (bm->totedge == 0 && bm->totface == 0) {
- /* cloud mesh */
- return hashfunc(&bm->totvert, sizeof(int), hash);
- }
-
- BM_ITER_MESH(f, &iter, bm, BM_FACES_OF_MESH) {
- BM_elem_flag_set(f, BM_ELEM_TAG, false);
- }
-
- /* todo -- have a deeper look onto how we can do this the fastest and safest way */
- BM_ITER_MESH(v, &iter, bm, BM_VERTS_OF_MESH) {
- if (v->e) {
- hash = hashedge_topo(v->e, hash);
- if (v->e->l && !BM_elem_flag_test_bool(v->e->l->f, BM_ELEM_TAG)) {
- hash = hashloop_topo(v->e->l, hash);
- hash = hashface_topo(v->e->l->f, hash);
- BM_elem_flag_set(v->e->l->f, BM_ELEM_TAG, true);
- }
- }
- }
-
- BM_ITER_MESH(f, &iter, bm, BM_FACES_OF_MESH) {
- BM_elem_flag_set(f, BM_ELEM_TAG, false);
- }
-
- return hash;
-}
-
void BKE_editmesh_topochange_calc(BMEditMesh *em)
{
- em->topochange.topohash = bmesh_topohash(em->bm);
- memcpy(&em->topochange.totvert, &em->bm->totvert, sizeof(int) * 4);
+ em->topochange.topohash = BM_mesh_topology_hash(em->bm);
+ em->topochange.totvert = em->bm->totvert;
+ em->topochange.totedge = em->bm->totedge;
+ em->topochange.totloop = em->bm->totloop;
+ em->topochange.totface = em->bm->totface;
}
-
bool BKE_editmesh_topo_has_changed(BMEditMesh *em)
{
- /* fast way to compare em->bm->totvert/totface/totetc with topochange */
- if (!memcmp(&em->bm->totvert, &em->topochange.totvert, sizeof(int) * 4)) {
- int hash = bmesh_topohash(em->bm);
+ if (em->bm->totvert == em->topochange.totvert || em->bm->totedge == em->topochange.totedge ||
+ em->bm->totloop == em->topochange.totloop || em->bm->totface == em->topochange.totface)
+ {
+ int hash = BM_mesh_topology_hash(em->bm);
if (hash == em->topochange.topohash)
return false;
else return true;
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c
index ca40cf9..c2ee154 100644
--- a/source/blender/bmesh/intern/bmesh_queries.c
+++ b/source/blender/bmesh/intern/bmesh_queries.c
@@ -2350,6 +2350,140 @@ int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_inde
return group_curr;
}
+/* TOPO hashing helpers. */
+/* murmur2A hashing func. */
+/* TODO: should go into BLI! */
+
+#define MM2A_M 0x5bd1e995
+
+#define MM2A_MIX(h, k) \
+{ \
+ (k) *= MM2A_M; \
+ (k) ^= (k) >> 24; \
+ (k) *= MM2A_M; \
+ (h) *= ((h) * MM2A_M) ^ (k); \
+} (void)0
+
+typedef struct Murmur2A {
+ uint32_t hash;
+ uint32_t tail;
+ uint32_t count;
+ uint32_t size;
+} Murmur2A;
+
+static void mm2a_mix_tail(Murmur2A *mm2, const unsigned char *data, size_t len)
+{
+ while (len && ((len < 4) || mm2->count)) {
+ mm2->tail |= *(uint32_t *)(data++) << (mm2->count * 8);
+
+ mm2->count++;
+ len--;
+
+ if (mm2->count == 4) {
+ MM2A_MIX(mm2->hash, mm2->tail);
+ mm2->tail = 0;
+ mm2->count = 0;
+ }
+ }
+}
+
+static void mm2a_init(Murmur2A *mm2, uint32_t seed)
+{
+ mm2->hash = seed;
+ mm2->tail = 0;
+ mm2->count = 0;
+ mm2->size = 0;
+}
+
+static void mm2a_add(Murmur2A *mm2, const unsigned char *data, size_t len)
+{
+ mm2->size += (uint32_t)len;
+
+ mm2a_mix_tail(mm2, data, len);
+
+ for (; len >= 4; data += 4, len -= 4) {
+ uint32_t k = *(uint32_t *)data;
+
+ MM2A_MIX(mm2->hash, k);
+ }
+
+ mm2a_mix_tail(mm2, data, len);
+}
+
+static void mm2a_add_int(Murmur2A *mm2, int data)
+{
+ mm2a_add(mm2, (const unsigned char *)&data, sizeof(data));
+}
+
+static uint32_t mm2a_end(Murmur2A *mm2)
+{
+ MM2A_MIX(mm2->hash, mm2->tail);
+ MM2A_MIX(mm2->hash, mm2->size);
+
+ mm2->hash ^= mm2->hash >> 13;
+ mm2->hash *= MM2A_M;
+ mm2->hash ^= mm2->hash >> 15;
+
+ return mm2->hash;
+}
+
+/**
+ * Calculate a hash of current topology.
+ *
+ * \param bm The BMesh.
+ * \return The hash, as an unsigned integer.
+ *
+ * \note We use vertex indices as core 'reference'.
+ */
+unsigned int BM_mesh_topology_hash(BMesh *bm)
+{
+ BMIter iter;
+ BMEdge *e;
+ BMLoop *l;
+ BMFace *f;
+
+ Murmur2A mm2;
+
+ unsigned int seed = (unsigned int)(bm->totvert + bm->totedge + bm->totloop + bm->totface);
+
+ if (!seed) {
+ return seed;
+ }
+
+ if (bm->totedge == 0) {
+ /* Cloud mesh, only vertices, totvert is good enough. */
+ return seed;
+ }
+
+ /* Now, we need vert indices! */
+ BM_mesh_elem_index_ensure(bm, BM_VERT);
+
+ /* Init the murmur hash. */
+ mm2a_init(&mm2, seed);
+
+ /* Compute edge topology, using only vert indices. */
+ BM_ITER_MESH(e, &iter, bm, BM_EDGES_OF_MESH) {
+ /* Edge topology is fully defined by its two vertices. */
+ mm2a_add_int(&mm2, BM_elem_index_get(e->v1));
+ mm2a_add_int(&mm2, BM_elem_index_get(e->v2));
+ }
+
+ if (bm->totface == 0) {
+ /* No face (nor loop), we are done. */
+ return mm2a_end(&mm2);
+ }
+
+ /* Else, we have to check all faces too - it *is* possible to change topology without affecting edges! */
+ BM_ITER_MESH(f, &iter, bm, BM_FACES_OF_MESH) {
+ /* Face topology is fully defined by its vertices and their order in it. */
+ BM_ITER_ELEM(l, &iter, f, BM_LOOPS_OF_FACE) {
+ mm2a_add_int(&mm2, BM_elem_index_get(l->v));
+ }
+ }
+
+ return mm2a_end(&mm2);
+}
+
float bmesh_subd_falloff_calc(const int falloff, float val)
{
switch (falloff) {
diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h
index c8578a8..e536601 100644
--- a/source/blender/bmesh/intern/bmesh_queries.h
+++ b/source/blender/bmesh/intern/bmesh_queries.h
@@ -151,6 +151,8 @@ int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_in
BMElemFilterFunc filter_fn, void *user_data,
const char hflag_test) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+unsigned int BM_mesh_topology_hash(BMesh *bm);
+
/* not really any good place to put this */
float bmesh_subd_falloff_calc(const int falloff, float val) ATTR_WARN_UNUSED_RESULT;
More information about the Bf-blender-cvs
mailing list