Dyntopo:

Store PBVH node ID in CustomData. This avoids a number of hash deletions
and checks/insertions on big hashes.

9 files changed, 143 insertions, 98 deletions

diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c
index 61261959ea8..0309e7defbe 100644
--- a/source/blender/blenkernel/intern/customdata.c
+++ b/source/blender/blenkernel/intern/customdata.c
@@ -1037,6 +1037,17 @@ static void layerDefault_mvert_skin(void *data, int count)
 	}
 }
 
+static void layerDefault_dyntopo_node(void *data, int count)
+{
+	int *indices = data;
+	int i;
+
+	for (i = 0; i < count; i++) {
+		indices[i] = DYNTOPO_NODE_NONE;
+	}
+}
+
+
 static void layerInterp_mvert_skin(void **sources, const float *weights,
                                    const float *UNUSED(sub_weights),
                                    int count, void *dest)
@@ -1172,6 +1183,8 @@ static const LayerTypeInfo LAYERTYPEINFO[CD_NUMTYPES] = {
 	{sizeof(float[4]), "", 0, NULL, NULL, NULL, NULL, NULL, NULL},
 	/* 40: CD_TESSLOOPNORMAL */
 	{sizeof(short[4][3]), "", 0, NULL, NULL, NULL, NULL, NULL, NULL},
+    /* 41: CD_DYNTOPO_NODE */
+	{sizeof(int), "", 0, NULL, NULL, NULL, NULL, NULL, layerDefault_dyntopo_node},
 };
 
 /* note, numbers are from trunk and need updating for bmesh */
@@ -1188,6 +1201,7 @@ static const char *LAYERTYPENAMES[CD_NUMTYPES] = {
 	/* 30-34 */ "CDSubSurfCrease", "CDOrigSpaceLoop", "CDPreviewLoopCol", "CDBMElemPyPtr", "CDPaintMask",
 	/* 35-36 */ "CDGridPaintMask", "CDMVertSkin",
 	/* 37-40 */ "CDFreestyleEdge", "CDFreestyleFace", "CDMLoopTangent", "CDTessLoopNormal",
+    /* 41 */ "CDDyntopoNode"
 };
 
 
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index d568d6183e6..a0007fe075f 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -618,11 +618,6 @@ void BKE_pbvh_free(PBVH *bvh)
 	if (bvh->prim_indices)
 		MEM_freeN(bvh->prim_indices);
 
-	if (bvh->bm_vert_to_node)
-		BLI_ghash_free(bvh->bm_vert_to_node, NULL, NULL);
-	if (bvh->bm_face_to_node)
-		BLI_ghash_free(bvh->bm_face_to_node, NULL, NULL);
-
 	MEM_freeN(bvh);
 }
 
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 80d92f7c3a1..cca24682f95 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -46,7 +46,7 @@
 /****************************** Building ******************************/
 
 /* Update node data after splitting */
-static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index)
+static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index, const int cd_vert_node_offset, const int cd_face_node_offset)
 {
 	GSetIterator gs_iter;
 	PBVHNode *n = &bvh->nodes[node_index];
@@ -62,22 +62,21 @@ static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index)
 		BMLoop *l_iter;
 		BMLoop *l_first;
 		BMVert *v;
-		void *node_val = SET_INT_IN_POINTER(node_index);
 
 		/* Update ownership of faces */
-		BLI_ghash_insert(bvh->bm_face_to_node, f, node_val);
+		BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
 
-		/* Update vertices */
+		        /* Update vertices */
 		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 		do {
 			v = l_iter->v;
 			if (!BLI_gset_haskey(n->bm_unique_verts, v)) {
-				if (BLI_ghash_haskey(bvh->bm_vert_to_node, v)) {
+				if (BM_ELEM_CD_GET_INT(v, cd_vert_node_offset) != DYNTOPO_NODE_NONE) {
 					BLI_gset_reinsert(n->bm_other_verts, v, NULL);
 				}
 				else {
 					BLI_gset_insert(n->bm_unique_verts, v);
-					BLI_ghash_insert(bvh->bm_vert_to_node, v, node_val);
+					BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
 				}
 			}
 			/* Update node bounding box */
@@ -97,7 +96,8 @@ static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index)
 }
 
 /* Recursively split the node if it exceeds the leaf_limit */
-static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
+static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index,
+                                  const int cd_vert_node_offset, const int cd_face_node_offset)
 {
 	GSet *empty, *other;
 	GSetIterator gs_iter;
@@ -110,7 +110,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
 
 	if (BLI_gset_size(n->bm_faces) <= bvh->leaf_limit) {
 		/* Node limit not exceeded */
-		pbvh_bmesh_node_finalize(bvh, node_index);
+		pbvh_bmesh_node_finalize(bvh, node_index, cd_vert_node_offset, cd_face_node_offset);
 		return;
 	}
 
@@ -179,7 +179,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
 	if (n->bm_unique_verts) {
 		GSET_ITER (gs_iter, n->bm_unique_verts) {
 			BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
-			BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
+			BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, DYNTOPO_NODE_NONE);
 		}
 		BLI_gset_free(n->bm_unique_verts, NULL);
 	}
@@ -187,7 +187,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
 	/* Unclaim faces */
 	GSET_ITER (gs_iter, n->bm_faces) {
 		BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
-		BLI_ghash_remove(bvh->bm_face_to_node, f, NULL, NULL);
+		BM_ELEM_CD_SET_INT(f, cd_face_node_offset, DYNTOPO_NODE_NONE);
 	}
 	BLI_gset_free(n->bm_faces, NULL);
 
@@ -210,8 +210,8 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
 	
 	/* Recurse */
 	c1 = c2 = NULL;
-	pbvh_bmesh_node_split(bvh, prim_bbc, children);
-	pbvh_bmesh_node_split(bvh, prim_bbc, children + 1);
+	pbvh_bmesh_node_split(bvh, prim_bbc, children, cd_vert_node_offset, cd_face_node_offset);
+	pbvh_bmesh_node_split(bvh, prim_bbc, children + 1, cd_vert_node_offset, cd_face_node_offset);
 
 	/* Array maybe reallocated, update current node pointer */
 	n = &bvh->nodes[node_index];
@@ -224,7 +224,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
 }
 
 /* Recursively split the node if it exceeds the leaf_limit */
-static bool pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index)
+static bool pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index, const int cd_vert_node_offset, const int cd_face_node_offset)
 {
 	GHash *prim_bbc;
 	GSet *bm_faces;
@@ -260,7 +260,7 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index)
 		BLI_ghash_insert(prim_bbc, f, bbc);
 	}
 
-	pbvh_bmesh_node_split(bvh, prim_bbc, node_index);
+	pbvh_bmesh_node_split(bvh, prim_bbc, node_index, cd_vert_node_offset, cd_face_node_offset);
 
 	BLI_ghash_free(prim_bbc, NULL, NULL);
 	MEM_freeN(bbc_array);
@@ -270,13 +270,12 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index)
 
 /**********************************************************************/
 
-static PBVHNode *pbvh_bmesh_node_lookup(PBVH *bvh, GHash *map, void *key)
+static PBVHNode *pbvh_bmesh_node_lookup(PBVH *bvh, void *key, const int cd_node_offset)
 {
-	int node_index;
+	int node_index = BM_ELEM_CD_GET_INT((BMElem *)key, cd_node_offset);
 
-	BLI_assert(BLI_ghash_haskey(map, key));
+	BLI_assert(node_index != DYNTOPO_NODE_NONE);
 
-	node_index = GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key));
 	BLI_assert(node_index < bvh->totnode);
 
 	return &bvh->nodes[node_index];
@@ -285,16 +284,16 @@ static PBVHNode *pbvh_bmesh_node_lookup(PBVH *bvh, GHash *map, void *key)
 static BMVert *pbvh_bmesh_vert_create(PBVH *bvh, int node_index,
                                       const float co[3],
                                       const BMVert *example,
-                                      const int cd_vert_mask_offset)
+                                      const int cd_vert_mask_offset,
+                                      const int cd_vert_node_offset)
 {
 	BMVert *v = BM_vert_create(bvh->bm, co, example, BM_CREATE_NOP);
-	void *val = SET_INT_IN_POINTER(node_index);
 	PBVHNode *node = &bvh->nodes[node_index];
 
 	BLI_assert((bvh->totnode == 1 || node_index) && node_index <= bvh->totnode);
 
 	BLI_gset_insert(node->bm_unique_verts, v);
-	BLI_ghash_insert(bvh->bm_vert_to_node, v, val);
+	BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
 
 	node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
 
@@ -306,10 +305,9 @@ static BMVert *pbvh_bmesh_vert_create(PBVH *bvh, int node_index,
 
 static BMFace *pbvh_bmesh_face_create(PBVH *bvh, int node_index,
                                       BMVert *v_tri[3], BMEdge *e_tri[3],
-                                      const BMFace *f_example)
+                                      const BMFace *f_example, const int cd_face_node_offset)
 {
 	BMFace *f;
-	void *val = SET_INT_IN_POINTER(node_index);
 	PBVHNode *node = &bvh->nodes[node_index];
 
 	/* ensure we never add existing face */
@@ -318,25 +316,21 @@ static BMFace *pbvh_bmesh_face_create(PBVH *bvh, int node_index,
 	f = BM_face_create(bvh->bm, v_tri, e_tri, 3, f_example, BM_CREATE_NOP);
 	f->head.hflag = f_example->head.hflag;
 
-	BLI_assert(!BLI_ghash_haskey(bvh->bm_face_to_node, f));
+	BLI_gset_insert(node->bm_faces, f);
+	BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
 
-	{
-		BLI_gset_insert(node->bm_faces, f);
-		BLI_ghash_insert(bvh->bm_face_to_node, f, val);
-
-		/* mark node for update */
-		node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateNormals;
-		node->flag &= ~PBVH_FullyHidden;
+	/* mark node for update */
+	node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateNormals;
+	node->flag &= ~PBVH_FullyHidden;
 
-		/* Log the new face */
-		BM_log_face_added(bvh->bm_log, f);
-	}
+	/* Log the new face */
+	BM_log_face_added(bvh->bm_log, f);
 
 	return f;
 }
 
 /* Return the number of faces in 'node' that use vertex 'v' */
-static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v)
+static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v, const int cd_face_node_offset)
 {
 	BMIter bm_iter;
 	BMFace *f;
@@ -345,7 +339,7 @@ static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v)
 	BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
 		PBVHNode *f_node;
 
-		f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+		f_node = pbvh_bmesh_node_lookup(bvh, f, cd_face_node_offset);
 
 		if (f_node == node)
 			count++;
@@ -355,18 +349,20 @@ static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v)
 }
 
 /* Return a node that uses vertex 'v' other than its current owner */
-static PBVHNode *pbvh_bmesh_vert_other_node_find(PBVH *bvh, BMVert *v)
+static PBVHNode *pbvh_bmesh_vert_other_node_find(PBVH *bvh, BMVert *v,
+                                                 const int cd_vert_node_offset,
+                                                 const int cd_face_node_offset)
 {
 	BMIter bm_iter;
 	BMFace *f;
 	PBVHNode *current_node;
 
-	current_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+	current_node = pbvh_bmesh_node_lookup(bvh, v, cd_vert_node_offset);
 
 	BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
 		PBVHNode *f_node;
 
-		f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+		f_node = pbvh_bmesh_node_lookup(bvh, f, cd_face_node_offset);
 
 		if (f_node != current_node)
 			return f_node;
@@ -376,11 +372,11 @@ static PBVHNode *pbvh_bmesh_vert_other_node_find(PBVH *bvh, BMVert *v)
 }
 
 static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner,
-                                               BMVert *v)
+                                               BMVert *v, const int cd_vert_node_offset)
 {
 	PBVHNode *current_owner;
 
-	current_owner = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+	current_owner = pbvh_bmesh_node_lookup(bvh, v, cd_vert_node_offset);
 	/* mark node for update */
 	current_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
 
@@ -391,8 +387,7 @@ static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner,
 	BLI_gset_remove(current_owner->bm_unique_verts, v, NULL);
 
 	/* Set new ownership */
-	BLI_ghash_reinsert(bvh->bm_vert_to_node, v,
-	                   SET_INT_IN_POINTER(new_owner - bvh->nodes), NULL, NULL);
+	BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, new_owner - bvh->nodes);
 	BLI_gset_insert(new_owner->bm_unique_verts, v);
 	BLI_gset_remove(new_owner->bm_other_verts, v, NULL);
 	BLI_assert(!BLI_gset_haskey(new_owner->bm_other_verts, v));
@@ -401,20 +396,19 @@ static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner,
 	new_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
 }
 
-static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v)
+static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v, const int cd_vert_node_offset, const int cd_face_node_offset)
 {
 	PBVHNode *v_node;
 	BMIter bm_iter;
 	BMFace *f;
 
-	BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
-	v_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+	v_node = pbvh_bmesh_node_lookup(bvh, v, cd_vert_node_offset);
 	BLI_gset_remove(v_node->bm_unique_verts, v, NULL);
-	BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
+	BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, DYNTOPO_NODE_NONE);
 
 	/* Have to check each neighboring face's node */
 	BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
-		PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+		PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, f, cd_face_node_offset);
 
 		f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
 
@@ -426,7 +420,7 @@ static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v)
 	}
 }
 
-static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f)
+static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f, const int cd_vert_node_offset, const int cd_face_node_offset)
 {
 	PBVHNode *f_node;
 	BMVert *v;
@@ -434,23 +428,23 @@ static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f)
 	BMLoop *l_iter;
 	BMLoop *l_first;
 
-	f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+	f_node = pbvh_bmesh_node_lookup(bvh, f, cd_face_node_offset);
 
 	/* Check if any of this face's vertices need to be removed
 	 * from the node */
 	l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 	do {
 		v = l_iter->v;
-		if (pbvh_bmesh_node_vert_use_count(bvh, f_node, v) == 1) {
+		if (pbvh_bmesh_node_vert_use_count(bvh, f_node, v, cd_face_node_offset) == 1) {
 			if (BLI_gset_haskey(f_node->bm_unique_verts, v)) {
 				/* Find a different node that uses 'v' */
 				PBVHNode *new_node;
 
-				new_node = pbvh_bmesh_vert_other_node_find(bvh, v);
+				new_node = pbvh_bmesh_vert_other_node_find(bvh, v, cd_vert_node_offset, cd_face_node_offset);
 				BLI_assert(new_node || BM_vert_face_count(v) == 1);
 
 				if (new_node) {
-					pbvh_bmesh_vert_ownership_transfer(bvh, new_node, v);
+					pbvh_bmesh_vert_ownership_transfer(bvh, new_node, v, cd_vert_node_offset);
 				}
 			}
 			else {
@@ -462,7 +456,7 @@ static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f)
 
 	/* Remove face from node and top level */
 	BLI_gset_remove(f_node->bm_faces, f, NULL);
-	BLI_ghash_remove(bvh->bm_face_to_node, f, NULL, NULL);
+	BM_ELEM_CD_SET_INT(f, cd_face_node_offset, DYNTOPO_NODE_NONE);
 
 	/* Log removed face */
 	BM_log_face_removed(bvh->bm_log, f);
@@ -512,6 +506,8 @@ typedef struct {
 	BLI_mempool *pool;
 	BMesh *bm;
 	int cd_vert_mask_offset;
+	int cd_vert_node_offset;
+	int cd_face_node_offset;
 } EdgeQueueContext;
 
 static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
@@ -705,9 +701,8 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, PBVH *bvh,
 	/* Create a new vertex in current node at the edge's midpoint */
 	mid_v3_v3v3(mid, e->v1->co, e->v2->co);
 
-	node_index = GET_INT_FROM_POINTER(BLI_ghash_lookup(bvh->bm_vert_to_node,
-	                                                   e->v1));
-	v_new = pbvh_bmesh_vert_create(bvh, node_index, mid, e->v1, eq_ctx->cd_vert_mask_offset);
+	node_index = BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset);
+	v_new = pbvh_bmesh_vert_create(bvh, node_index, mid, e->v1, eq_ctx->cd_vert_mask_offset, eq_ctx->cd_vert_node_offset);
 
 	/* update paint mask */
 	if (eq_ctx->cd_vert_mask_offset != -1) {
@@ -726,12 +721,10 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, PBVH *bvh,
 		BMVert *v_opp, *v1, *v2;
 		BMVert *v_tri[3];
 		BMEdge *e_tri[3];
-		void *nip;
 		int ni;
 
 		BLI_assert(f_adj->len == 3);
-		nip = BLI_ghash_lookup(bvh->bm_face_to_node, f_adj);
-		ni = GET_INT_FROM_POINTER(nip);
+		ni = BM_ELEM_CD_GET_INT(f_adj, eq_ctx->cd_face_node_offset);
 
 		/* Find the vertex not in the edge */
 		v_opp = l_adj->prev->v;
@@ -743,14 +736,14 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, PBVH *bvh,
 		v2 = l_adj->next->v;
 
 		if (ni != node_index && i == 0)
-			pbvh_bmesh_vert_ownership_transfer(bvh, &bvh->nodes[ni], v_new);
+			pbvh_bmesh_vert_ownership_transfer(bvh, &bvh->nodes[ni], v_new, eq_ctx->cd_vert_node_offset);
 
 		/* Create two new faces */
 		v_tri[0] = v1;
 		v_tri[1] = v_new;
 		v_tri[2] = v_opp;
 		bm_edges_from_tri(bvh->bm, v_tri, e_tri);
-		f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_adj);
+		f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_adj, eq_ctx->cd_face_node_offset);
 		long_edge_queue_face_add(eq_ctx, f_new);
 
 		v_tri[0] = v_new;
@@ -759,11 +752,11 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, PBVH *bvh,
 		e_tri[0] = BM_edge_create(bvh->bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE);
 		e_tri[2] = e_tri[1];  /* switched */
 		e_tri[1] = BM_edge_create(bvh->bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE);
-		f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_adj);
+		f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_adj, eq_ctx->cd_face_node_offset);
 		long_edge_queue_face_add(eq_ctx, f_new);
 
 		/* Delete original */
-		pbvh_bmesh_face_remove(bvh, f_adj);
+		pbvh_bmesh_face_remove(bvh, f_adj, eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
 		BM_face_kill(bvh->bm, f_adj);
 
 		/* Ensure new vertex is in the node */
@@ -811,8 +804,8 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *bvh,
 		 * possible that an edge collapse has deleted adjacent faces
 		 * and the node has been split, thus leaving wire edges and
 		 * associated vertices. */
-		if (!BLI_ghash_haskey(bvh->bm_vert_to_node, e->v1) ||
-		    !BLI_ghash_haskey(bvh->bm_vert_to_node, e->v2))
+		if ((BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE) ||
+		    (BM_ELEM_CD_GET_INT(e->v2, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE))
 		{
 			continue;
 		}
@@ -830,13 +823,13 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
                                      GSet *deleted_verts,
                                      BLI_Buffer *edge_loops,
                                      BLI_Buffer *deleted_faces,
-                                     int cd_vert_mask_offset)
+                                     EdgeQueueContext *eq_ctx)
 {
 	BMIter bm_iter;
 	BMFace *f;
 	BMVert *v_del, *v_conn;
 	int i;
-	float mask_v1 = BM_ELEM_CD_GET_FLOAT(v1, cd_vert_mask_offset);
+	float mask_v1 = BM_ELEM_CD_GET_FLOAT(v1, eq_ctx->cd_vert_mask_offset);
 
 	/* one of the two vertices may be masked, select the correct one for deletion */
 	if (mask_v1 < 1.0f) {
@@ -852,14 +845,14 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 	pbvh_bmesh_edge_loops(edge_loops, e);
 
 	/* Remove the merge vertex from the PBVH */
-	pbvh_bmesh_vert_remove(bvh, v_del);
+	pbvh_bmesh_vert_remove(bvh, v_del, eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
 
 	/* Remove all faces adjacent to the edge */
 	for (i = 0; i < edge_loops->count; i++) {
 		BMLoop *l_adj = BLI_buffer_at(edge_loops, BMLoop *, i);
 		BMFace *f_adj = l_adj->f;
 
-		pbvh_bmesh_face_remove(bvh, f_adj);
+		pbvh_bmesh_face_remove(bvh, f_adj, eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
 		BM_face_kill(bvh->bm, f_adj);
 	}
 
@@ -898,10 +891,10 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 		}
 		else {
 			BMEdge *e_tri[3];
-			n = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+			n = pbvh_bmesh_node_lookup(bvh, f, eq_ctx->cd_face_node_offset);
 			ni = n - bvh->nodes;
 			bm_edges_from_tri(bvh->bm, v_tri, e_tri);
-			pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f);
+			pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f, eq_ctx->cd_face_node_offset);
 
 			/* Ensure that v_conn is in the new face's node */
 			if (!BLI_gset_haskey(n->bm_unique_verts, v_conn) &&
@@ -934,7 +927,7 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 		for (j = 0; j < 3; j++) {
 			if (v_tri[j] != v_del && BM_vert_face_count(v_tri[j]) == 1) {
 				BLI_gset_insert(deleted_verts, v_tri[j]);
-				pbvh_bmesh_vert_remove(bvh, v_tri[j]);
+				pbvh_bmesh_vert_remove(bvh, v_tri[j], eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
 			}
 			else {
 				v_tri[j] = NULL;
@@ -942,7 +935,7 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 		}
 
 		/* Remove the face */
-		pbvh_bmesh_face_remove(bvh, f_del);
+		pbvh_bmesh_face_remove(bvh, f_del, eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
 		BM_face_kill(bvh->bm, f_del);
 
 		/* Check if any of the face's edges are now unused by any
@@ -955,7 +948,7 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 		/* Delete unused vertices */
 		for (j = 0; j < 3; j++) {
 			if (v_tri[j]) {
-				BM_log_vert_removed(bvh->bm_log, v_tri[j], cd_vert_mask_offset);
+				BM_log_vert_removed(bvh->bm_log, v_tri[j], eq_ctx->cd_vert_mask_offset);
 				BM_vert_kill(bvh->bm, v_tri[j]);
 			}
 		}
@@ -964,14 +957,14 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 	/* Move v_conn to the midpoint of v_conn and v_del (if v_conn still exists, it
 	 * may have been deleted above) */
 	if (!BLI_gset_haskey(deleted_verts, v_conn)) {
-		BM_log_vert_before_modified(bvh->bm_log, v_conn, cd_vert_mask_offset);
+		BM_log_vert_before_modified(bvh->bm_log, v_conn, eq_ctx->cd_vert_mask_offset);
 		mid_v3_v3v3(v_conn->co, v_conn->co, v_del->co);
 	}
 
 	/* Delete v_del */
 	BLI_assert(BM_vert_face_count(v_del) == 0);
 	BLI_gset_insert(deleted_verts, v_del);
-	BM_log_vert_removed(bvh->bm_log, v_del, cd_vert_mask_offset);
+	BM_log_vert_removed(bvh->bm_log, v_del, eq_ctx->cd_vert_mask_offset);
 	BM_vert_kill(bvh->bm, v_del);
 }
 
@@ -1013,8 +1006,8 @@ static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx,
 		 * possible that an edge collapse has deleted adjacent faces
 		 * and the node has been split, thus leaving wire edges and
 		 * associated vertices. */
-		if (!BLI_ghash_haskey(bvh->bm_vert_to_node, e->v1) ||
-		    !BLI_ghash_haskey(bvh->bm_vert_to_node, e->v2))
+		if ((BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE) ||
+		    (BM_ELEM_CD_GET_INT(e->v2, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE))
 		{
 			continue;
 		}
@@ -1023,7 +1016,7 @@ static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx,
 
 		pbvh_bmesh_collapse_edge(bvh, e, v1, v2,
 		                         deleted_verts, edge_loops,
-		                         deleted_faces, eq_ctx->cd_vert_mask_offset);
+		                         deleted_faces, eq_ctx);
 	}
 
 	BLI_gset_free(deleted_verts, NULL);
@@ -1158,13 +1151,14 @@ void BKE_pbvh_build_bmesh(PBVH *bvh, BMesh *bm, bool smooth_shading, BMLog *log)
 	PBVHNode *n;
 	int node_index = 0;
 
+	const int cd_vert_node_offset = CustomData_get_offset(&bm->vdata, CD_DYNTOPO_NODE);
+	const int cd_face_node_offset = CustomData_get_offset(&bm->pdata, CD_DYNTOPO_NODE);
+
 	bvh->bm = bm;
 
 	BKE_pbvh_bmesh_detail_size_set(bvh, 0.75);
 
 	bvh->type = PBVH_BMESH;
-	bvh->bm_face_to_node = BLI_ghash_ptr_new("bm_face_to_node");
-	bvh->bm_vert_to_node = BLI_ghash_ptr_new("bm_vert_to_node");
 	bvh->bm_log = log;
 
 	/* TODO: choose leaf limit better */
@@ -1184,8 +1178,8 @@ void BKE_pbvh_build_bmesh(PBVH *bvh, BMesh *bm, bool smooth_shading, BMLog *log)
 
 	/* Recursively split the node until it is under the limit; if no
 	 * splitting occurs then finalize the existing leaf node */
-	if (!pbvh_bmesh_node_limit_ensure(bvh, node_index))
-		pbvh_bmesh_node_finalize(bvh, 0);
+	if (!pbvh_bmesh_node_limit_ensure(bvh, node_index, cd_vert_node_offset, cd_face_node_offset))
+		pbvh_bmesh_node_finalize(bvh, 0, cd_vert_node_offset, cd_face_node_offset);
 }
 
 /* Collapse short edges, subdivide long edges */
@@ -1196,6 +1190,8 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
 	BLI_buffer_declare_static(BMFace *, edge_loops, BLI_BUFFER_NOP, 2);
 	BLI_buffer_declare_static(BMFace *, deleted_faces, BLI_BUFFER_NOP, 32);
 	const int cd_vert_mask_offset = CustomData_get_offset(&bvh->bm->vdata, CD_PAINT_MASK);
+	const int cd_vert_node_offset = CustomData_get_offset(&bvh->bm->vdata, CD_DYNTOPO_NODE);
+	const int cd_face_node_offset = CustomData_get_offset(&bvh->bm->pdata, CD_DYNTOPO_NODE);
 
 	bool modified = false;
 	int n;
@@ -1203,7 +1199,7 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
 	if (mode & PBVH_Collapse) {
 		EdgeQueue q;
 		BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP);
-		EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset};
+		EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset};
 
 		short_edge_queue_create(&eq_ctx, bvh, center, radius);
 		modified |= !BLI_heap_is_empty(q.heap);
@@ -1216,7 +1212,7 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
 	if (mode & PBVH_Subdivide) {
 		EdgeQueue q;
 		BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP);
-		EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset};
+		EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset};
 
 		long_edge_queue_create(&eq_ctx, bvh, center, radius);
 		modified |= !BLI_heap_is_empty(q.heap);
@@ -1315,6 +1311,10 @@ void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node)
 void BKE_pbvh_bmesh_after_stroke(PBVH *bvh)
 {
 	int i;
+
+	const int cd_vert_node_offset = CustomData_get_offset(&bvh->bm->vdata, CD_DYNTOPO_NODE);
+	const int cd_face_node_offset = CustomData_get_offset(&bvh->bm->pdata, CD_DYNTOPO_NODE);
+
 	for (i = 0; i < bvh->totnode; i++) {
 		PBVHNode *n = &bvh->nodes[i];
 		if (n->flag & PBVH_Leaf) {
@@ -1323,7 +1323,7 @@ void BKE_pbvh_bmesh_after_stroke(PBVH *bvh)
 
 			/* Recursively split nodes that have gotten too many
 			 * elements */
-			pbvh_bmesh_node_limit_ensure(bvh, i);
+			pbvh_bmesh_node_limit_ensure(bvh, i, cd_vert_node_offset, cd_face_node_offset);
 		}
 	}
 }
diff --git a/source/blender/blenkernel/intern/pbvh_intern.h b/source/blender/blenkernel/intern/pbvh_intern.h
index 46f7a9b7b56..ef5828e8097 100644
--- a/source/blender/blenkernel/intern/pbvh_intern.h
+++ b/source/blender/blenkernel/intern/pbvh_intern.h
@@ -160,8 +160,6 @@ struct PBVH {
 
 	/* Dynamic topology */
 	BMesh *bm;
-	GHash *bm_face_to_node;
-	GHash *bm_vert_to_node;
 	float bm_max_edge_len;
 	float bm_min_edge_len;
 
diff --git a/source/blender/bmesh/bmesh_class.h b/source/blender/bmesh/bmesh_class.h
index ea7505bcba4..83b02764046 100644
--- a/source/blender/bmesh/bmesh_class.h
+++ b/source/blender/bmesh/bmesh_class.h
@@ -285,6 +285,12 @@ extern void bpy_bm_generic_invalidate(struct BPy_BMGeneric *self);
 typedef bool (*BMElemFilterFunc)(BMElem *, void *user_data);
 
 /* defines */
+#define BM_ELEM_CD_SET_INT(ele, offset, f) \
+	{ assert(offset != -1); *((int *)((char *)(ele)->head.data + (offset))) = (f); } (void)0
+
+#define BM_ELEM_CD_GET_INT(ele, offset) \
+	(assert(offset != -1), *((int *)((char *)(ele)->head.data + (offset))))
+
 #define BM_ELEM_CD_GET_VOID_P(ele, offset) \
 	(assert(offset != -1), (void *)((char *)(ele)->head.data + (offset)))
 
diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c
index 290acc49a8e..db500e00b75 100644
--- a/source/blender/editors/sculpt_paint/sculpt.c
+++ b/source/blender/editors/sculpt_paint/sculpt.c
@@ -4793,6 +4793,26 @@ void sculpt_pbvh_clear(Object *ob)
 	BKE_object_free_derived_caches(ob);
 }
 
+void sculpt_dyntopo_node_layers_reset(BMesh *bm)
+{
+	/* A bit lame, but for now just recreate the PBVH. The alternative
+	 * is to store changes to the PBVH in the undo stack. */
+	BMFace *f;
+	BMVert *v;
+	BMIter iter;
+	const int cd_vert_node_offset = CustomData_get_offset(&bm->vdata, CD_DYNTOPO_NODE);
+	const int cd_face_node_offset = CustomData_get_offset(&bm->pdata, CD_DYNTOPO_NODE);
+
+	/* clear the elements of the node information */
+	BM_ITER_MESH(v, &iter, bm, BM_VERTS_OF_MESH) {
+		BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, DYNTOPO_NODE_NONE);
+	}
+
+	BM_ITER_MESH(f, &iter, bm, BM_FACES_OF_MESH) {
+		BM_ELEM_CD_SET_INT(f, cd_face_node_offset, DYNTOPO_NODE_NONE);
+	}
+}
+
 void sculpt_update_after_dynamic_topology_toggle(bContext *C)
 {
 	Scene *scene = CTX_data_scene(C);
@@ -4825,6 +4845,8 @@ void sculpt_dynamic_topology_enable(bContext *C)
 	BM_mesh_bm_from_me(ss->bm, me, true, true, ob->shapenr);
 	sculpt_dynamic_topology_triangulate(ss->bm);
 	BM_data_layer_add(ss->bm, &ss->bm->vdata, CD_PAINT_MASK);
+	BM_data_layer_add(ss->bm, &ss->bm->vdata, CD_DYNTOPO_NODE);
+	BM_data_layer_add(ss->bm, &ss->bm->pdata, CD_DYNTOPO_NODE);
 	BM_mesh_normals_update(ss->bm);
 
 	/* Enable dynamic topology */
diff --git a/source/blender/editors/sculpt_paint/sculpt_intern.h b/source/blender/editors/sculpt_paint/sculpt_intern.h
index 9c0e937c35c..79fd388e332 100644
--- a/source/blender/editors/sculpt_paint/sculpt_intern.h
+++ b/source/blender/editors/sculpt_paint/sculpt_intern.h
@@ -42,6 +42,7 @@
 
 struct bContext;
 struct Brush;
+struct BMesh;
 struct KeyBlock;
 struct Mesh;
 struct MultiresModifierData;
@@ -67,6 +68,7 @@ bool sculpt_stroke_get_location(bContext *C, float out[3], const float mouse[2])
 
 /* Dynamic topology */
 void sculpt_pbvh_clear(Object *ob);
+void sculpt_dyntopo_node_layers_reset(struct BMesh *bm);
 void sculpt_update_after_dynamic_topology_toggle(bContext *C);
 void sculpt_dynamic_topology_enable(struct bContext *C);
 void sculpt_dynamic_topology_disable(struct bContext *C,
diff --git a/source/blender/editors/sculpt_paint/sculpt_undo.c b/source/blender/editors/sculpt_paint/sculpt_undo.c
index 724d093a48f..b0fd7faa70d 100644
--- a/source/blender/editors/sculpt_paint/sculpt_undo.c
+++ b/source/blender/editors/sculpt_paint/sculpt_undo.c
@@ -301,8 +301,7 @@ static void sculpt_undo_bmesh_restore_generic(bContext *C,
 			MEM_freeN(nodes);
 	}
 	else {
-		/* A bit lame, but for now just recreate the PBVH. The alternative
-		 * is to store changes to the PBVH in the undo stack. */
+		sculpt_dyntopo_node_layers_reset(ss->bm);
 		sculpt_pbvh_clear(ob);
 	}
 }
@@ -319,6 +318,8 @@ static void sculpt_undo_bmesh_enable(Object *ob,
 	/* Create empty BMesh and enable logging */
 	ss->bm = BM_mesh_create(&bm_mesh_allocsize_default);
 	BM_data_layer_add(ss->bm, &ss->bm->vdata, CD_PAINT_MASK);
+	BM_data_layer_add(ss->bm, &ss->bm->vdata, CD_DYNTOPO_NODE);
+	BM_data_layer_add(ss->bm, &ss->bm->pdata, CD_DYNTOPO_NODE);
 	me->flag |= ME_SCULPT_DYNAMIC_TOPOLOGY;
 
 	/* Restore the BMLog using saved entries */
diff --git a/source/blender/makesdna/DNA_customdata_types.h b/source/blender/makesdna/DNA_customdata_types.h
index d1844b34a0a..4869c9a74f1 100644
--- a/source/blender/makesdna/DNA_customdata_types.h
+++ b/source/blender/makesdna/DNA_customdata_types.h
@@ -63,9 +63,10 @@ typedef struct CustomDataExternal {
  * layers, each with a data type (e.g. MTFace, MDeformVert, etc.). */
 typedef struct CustomData {
 	CustomDataLayer *layers;      /* CustomDataLayers, ordered by type */
-	int typemap[41];              /* runtime only! - maps types to indices of first layer of that type,
+	int typemap[42];              /* runtime only! - maps types to indices of first layer of that type,
 	                               * MUST be >= CD_NUMTYPES, but we cant use a define here.
 	                               * Correct size is ensured in CustomData_update_typemap assert() */
+	int pad;
 	int totlayer, maxlayer;       /* number of layers, size of layers array */
 	int totsize;                  /* in editmode, total size of all data layers */
 	struct BLI_mempool *pool;     /* (BMesh Only): Memory pool for allocation of blocks */
@@ -119,7 +120,9 @@ enum {
 	CD_FREESTYLE_FACE   = 38,
 	CD_MLOOPTANGENT     = 39,
 	CD_TESSLOOPNORMAL   = 40,
-	CD_NUMTYPES         = 41,
+
+	CD_DYNTOPO_NODE     = 41,
+	CD_NUMTYPES         = 42
 };
 
 /* Bits for CustomDataMask */
@@ -167,6 +170,8 @@ enum {
 #define CD_MASK_MLOOPTANGENT    (1LL << CD_MLOOPTANGENT)
 #define CD_MASK_TESSLOOPNORMAL  (1LL << CD_TESSLOOPNORMAL)
 
+#define CD_MASK_DYNTOPO_NODE    (1LL << CD_DYNTOPO_NODE)
+
 /* CustomData.flag */
 enum {
 	/* Indicates layer should not be copied by CustomData_from_template or CustomData_copy_data */
@@ -185,6 +190,8 @@ enum {
 #define MAX_MTFACE  8
 #define MAX_MCOL    8
 
+#define DYNTOPO_NODE_NONE -1
+
 #ifdef __cplusplus
 }
 #endif