[Bf-blender-cvs] [e9c28dd] soc-2014-shapekey: Implemented draft topology x17-based hashing in BKE_editmesh

[Grigory Revzin]

Commit: e9c28ddbbdbfc38a25edaf1e2f4d05e0ad272296
Author: Grigory Revzin
Date:   Fri May 16 03:19:36 2014 +0400
https://developer.blender.org/rBe9c28ddbbdbfc38a25edaf1e2f4d05e0ad272296

Implemented draft topology x17-based hashing in BKE_editmesh

===================================================================

M	source/blender/blenkernel/BKE_editmesh.h
M	source/blender/blenkernel/intern/editmesh.c

===================================================================

diff --git a/source/blender/blenkernel/BKE_editmesh.h b/source/blender/blenkernel/BKE_editmesh.h
index 38c8cf1..5a700ac 100644
--- a/source/blender/blenkernel/BKE_editmesh.h
+++ b/source/blender/blenkernel/BKE_editmesh.h
@@ -38,6 +38,12 @@ struct Scene;
 struct DerivedMesh;
 struct MeshStatVis;
 
+/* struct for storing data to determine if the mesh's topology has changed */
+typedef struct {
+	int totvert, totedge, totloop, totface;
+	int topohash;
+} EMTopoChangeData;
+
 /* ok: the EDBM module is for editmode bmesh stuff.  in contrast, the 
  *     BMEdit module is for code shared with blenkernel that concerns
  *     the BMEditMesh structure.
@@ -78,6 +84,10 @@ typedef struct BMEditMesh {
 	/* Object this editmesh came from (if it came from one) */
 	struct Object *ob;
 
+	/* used to know if the editmesh's topology has changed from a certain point in time,
+	 * use BKE_editmesh_topochange_calc/BKE_editmesh_topo_has_changed */
+	EMTopoChangeData topochange;
+
 	/*temp variables for x-mirror editing*/
 	int mirror_cdlayer; /* -1 is invalid */
 } BMEditMesh;
@@ -94,6 +104,12 @@ void        BKE_editmesh_update_linked_customdata(BMEditMesh *em);
 void        BKE_editmesh_color_free(BMEditMesh *em);
 void        BKE_editmesh_color_ensure(BMEditMesh *em, const char htype);
 
+/* calculates a topology-dependent hash to detect if topology has been modified later */
+void		BKE_editmesh_topochange_calc(BMEditMesh *em);
+
+/* checks if the topology has changed since last call to BKE_editmesh_syncdata_calc. Does not recalc! */
+bool		BKE_editmesh_topo_has_changed(BMEditMesh *em);
+
 /* editderivedmesh.c */
 /* should really be defined in editmesh.c, but they use 'EditDerivedBMesh' */
 void        BKE_editmesh_statvis_calc(BMEditMesh *em, struct DerivedMesh *dm,
diff --git a/source/blender/blenkernel/intern/editmesh.c b/source/blender/blenkernel/intern/editmesh.c
index 2247b91..3d41be7 100644
--- a/source/blender/blenkernel/intern/editmesh.c
+++ b/source/blender/blenkernel/intern/editmesh.c
@@ -246,3 +246,102 @@ void BKE_editmesh_color_ensure(BMEditMesh *em, const char htype)
 			break;
 	}
 }
+
+
+/* ==================== topology hashing ======================= */
+
+unsigned int x17_hash(const char *data, unsigned int len, unsigned int seed)
+{
+	unsigned int hash = seed + len;
+	for (; len & ~1; len -= 2, data += 2)
+		hash = (((hash * 17) + (data[0] - ' ')) * 17) + (data[1] - ' ');
+
+	if (len & 1)
+		hash = (hash * 17) + (data[0] - ' ');
+	return hash;
+}
+
+int hashfunc(void *data, int len)
+{
+	return (int) x17_hash(data, len, 0x27127127);
+}
+
+int hashloop_topo(BMLoop *l)
+{
+	/* skip header, don't track customdata */
+	return hashfunc(((char *)l) + sizeof(BMHeader), sizeof(BMLoop) - sizeof(BMHeader));
+}
+
+int hashface_topo(BMFace *f)
+{
+	/* skip header & flags & face normals and material */
+	int a = f->len + (int)f->l_first;
+	return hashfunc(&a, sizeof(int));
+}
+
+/* TODO better hashing */
+int bmesh_topohash(BMesh *bm)
+{
+	BMIter iter;
+	BMLoop *l;
+	BMFace *f;
+	BMEdge *e;
+	int i;
+	int j;
+	int hash = bm->totedge + bm->totvert + bm->totloop + bm->totface;
+
+	if (!hash) {
+		return 0;
+	}
+
+	if (bm->totface)
+	{
+		BM_ITER_MESH_INDEX(f, &iter, bm, BM_FACES_OF_MESH, i) {
+			hash += i * hashface_topo(f);
+			l = f->l_first;
+			int len3 = f->len * f->len * f->len;
+			for (j = 0; j < f->len; ++j) {
+				hash += (len3 + i - j) * hashloop_topo(l);
+				l = l->next;
+			}
+		}
+		/* this next cycle is to counter weird meshes like one face, one million wire edges*/
+		BM_ITER_MESH_INDEX(e, &iter, bm, BM_EDGES_OF_MESH, i) {
+			j = (int)e->v1 + (int)e->v2;
+			hash += hashfunc(&j, sizeof(int));
+		}
+	}
+	else {
+		if (bm->totedge == 0) {
+			/* cloud mesh */
+			return hashfunc(&bm->totvert, sizeof(int));
+		}
+		else {
+			/* wire mesh */
+			BM_ITER_MESH_INDEX(e, &iter, bm, BM_EDGES_OF_MESH, i) {
+				j = (int)e->v1 + (int)e->v2;
+				hash += hashfunc(&j, sizeof(int));
+			}
+		}
+	}
+	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);
+}
+
+
+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 (hash == em->topochange.topohash)
+			return false;
+		else return true;
+	}
+	return true;
+}