Dyntopo:
authorAntony Riakiotakis <kalast@gmail.com>
Wed, 16 Apr 2014 02:31:02 +0000 (05:31 +0300)
committerAntony Riakiotakis <kalast@gmail.com>
Wed, 16 Apr 2014 02:31:02 +0000 (05:31 +0300)
Store PBVH node ID in CustomData. This avoids a number of hash deletions
and checks/insertions on big hashes.

source/blender/blenkernel/intern/customdata.c
source/blender/blenkernel/intern/pbvh.c
source/blender/blenkernel/intern/pbvh_bmesh.c
source/blender/blenkernel/intern/pbvh_intern.h
source/blender/bmesh/bmesh_class.h
source/blender/editors/sculpt_paint/sculpt.c
source/blender/editors/sculpt_paint/sculpt_intern.h
source/blender/editors/sculpt_paint/sculpt_undo.c
source/blender/makesdna/DNA_customdata_types.h

index 61261959ea8db13d49a25b844f5673c3e4b6c50e..0309e7defbede56ef2b6b39bc5d8ae66f00be8bb 100644 (file)
@@ -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"
 };
 
 
index d568d6183e682d966951ebdd751a64b04c23ee34..a0007fe075fc42bae094fce0ff085f69bd10dbc0 100644 (file)
@@ -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);
 }
 
index 80d92f7c3a1bea7cead97e9d4a8592a02a94dabb..cca24682f952e9b6157219fa7b90051a7c81dde8 100644 (file)
@@ -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);
                }
        }
 }
index 46f7a9b7b565b6d668b969bb1a12928e5727e20c..ef5828e8097572e4eb74fa1aaa0ca34a521e3979 100644 (file)
@@ -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;
 
index ea7505bcba42a149941480f339c7b835c4346286..83b027640466096f80d024192153802611d76479 100644 (file)
@@ -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)))
 
index 290acc49a8ef5e7dc48acbf9c25fb3127e8cae7a..db500e00b75cb65fa0cad8f81db4af8b087606c9 100644 (file)
@@ -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 */
index 9c0e937c35caadbea08fcc309051d58e5b11f432..79fd388e3323090c4d61af801f629cca3b802727 100644 (file)
@@ -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,
index 724d093a48f823dafc66d2e12d0a8e90ad7b8eac..b0fd7faa70d4be5ce7898d3386f30274c6926706 100644 (file)
@@ -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 */
index d1844b34a0a8a8334a357dfa5e0ba38bfcda2f48..4869c9a74f1901246a699e39f66a9ef4f0114e99 100644 (file)
@@ -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