transform_snap_object: Better bvhtree creation management for editing multiple objects.
authorGermano <germano.costa@ig.com.br>
Mon, 23 Jul 2018 14:04:58 +0000 (11:04 -0300)
committerGermano <germano.costa@ig.com.br>
Mon, 23 Jul 2018 14:04:58 +0000 (11:04 -0300)
- Use the object referenced in `BMEditMesh` as the `ghash` key to save the bvhtrees in cache;
- Create a boundbox around edit_mesh to test the snap before creating bvhtree;
- Save the `edit_mesh`s bvhtree in the mesh bvh_cache;

This is a part of the D3504.

source/blender/blenkernel/BKE_bvhutils.h
source/blender/blenkernel/intern/bvhutils.c
source/blender/editors/transform/transform_snap_object.c

index d79a7eae53e8a2f754caba0088063aed0015c1d5..a0780a5be542f915ac843944290b60de7d1aa492 100644 (file)
@@ -102,7 +102,7 @@ typedef struct BVHTreeFromMesh {
  */
 BVHTree *bvhtree_from_editmesh_verts(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
-        float epsilon, int tree_type, int axis);
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache);
 BVHTree *bvhtree_from_editmesh_verts_ex(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
         const BLI_bitmap *mask, int verts_num_active,
@@ -115,7 +115,7 @@ BVHTree *bvhtree_from_mesh_verts_ex(
 
 BVHTree *bvhtree_from_editmesh_edges(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
-        float epsilon, int tree_type, int axis);
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache);
 BVHTree *bvhtree_from_editmesh_edges_ex(
         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
         const BLI_bitmap *edges_mask, int edges_num_active,
@@ -190,7 +190,9 @@ enum {
        BVHTREE_FROM_LOOSEVERTS      = 4,
        BVHTREE_FROM_LOOSEEDGES      = 5,
 
-       BVHTREE_FROM_EM_LOOPTRI      = 6,
+       BVHTREE_FROM_EM_VERTS        = 6,
+       BVHTREE_FROM_EM_EDGES        = 7,
+       BVHTREE_FROM_EM_LOOPTRI      = 8,
 };
 
 
index 1a7c4e2a4a08c40cc5906adc9ec9f0b817c5af37..19ac81b4bb7787a74fac7841b2255308f1774788 100644 (file)
@@ -495,12 +495,39 @@ BVHTree *bvhtree_from_editmesh_verts_ex(
 
 BVHTree *bvhtree_from_editmesh_verts(
         BVHTreeFromEditMesh *data, BMEditMesh *em,
-        float epsilon, int tree_type, int axis)
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache)
 {
-       return bvhtree_from_editmesh_verts_ex(
-               data, em,
-               NULL, -1,
-               epsilon, tree_type, axis);
+       if (bvh_cache) {
+               BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
+               data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree);
+               BLI_rw_mutex_unlock(&cache_rwlock);
+
+               if (data->cached == false) {
+                       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
+                       data->cached = bvhcache_find(
+                               *bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree);
+                       if (data->cached == false) {
+                               data->tree = bvhtree_from_editmesh_verts_ex(
+                                       data, em,
+                                       NULL, -1,
+                                       epsilon, tree_type, axis);
+
+                               /* Save on cache for later use */
+                               /* printf("BVHTree built and saved on cache\n"); */
+                               bvhcache_insert(
+                                       bvh_cache, data->tree, BVHTREE_FROM_EM_VERTS);
+                       }
+                       BLI_rw_mutex_unlock(&cache_rwlock);
+               }
+       }
+       else {
+               data->tree = bvhtree_from_editmesh_verts_ex(
+                       data, em,
+                       NULL, -1,
+                       epsilon, tree_type, axis);
+       }
+
+       return data->tree;
 }
 
 /**
@@ -649,12 +676,39 @@ BVHTree *bvhtree_from_editmesh_edges_ex(
 
 BVHTree *bvhtree_from_editmesh_edges(
         BVHTreeFromEditMesh *data, BMEditMesh *em,
-        float epsilon, int tree_type, int axis)
+        float epsilon, int tree_type, int axis, BVHCache **bvh_cache)
 {
-       return bvhtree_from_editmesh_edges_ex(
-               data, em,
-               NULL, -1,
-               epsilon, tree_type, axis);
+       if (bvh_cache) {
+               BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
+               data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
+               BLI_rw_mutex_unlock(&cache_rwlock);
+
+               if (data->cached == false) {
+                       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
+                       data->cached = bvhcache_find(
+                               *bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
+                       if (data->cached == false) {
+                               data->tree = bvhtree_from_editmesh_edges_ex(
+                                       data, em,
+                                       NULL, -1,
+                                       epsilon, tree_type, axis);
+
+                               /* Save on cache for later use */
+                               /* printf("BVHTree built and saved on cache\n"); */
+                               bvhcache_insert(
+                                       bvh_cache, data->tree, BVHTREE_FROM_EM_EDGES);
+                       }
+                       BLI_rw_mutex_unlock(&cache_rwlock);
+               }
+       }
+       else {
+               data->tree = bvhtree_from_editmesh_edges_ex(
+                       data, em,
+                       NULL, -1,
+                       epsilon, tree_type, axis);
+       }
+
+       return data->tree;
 }
 
 /**
@@ -1407,6 +1461,11 @@ BVHTree *BKE_bvhtree_from_mesh_get(
                                BLI_rw_mutex_unlock(&cache_rwlock);
                        }
                        break;
+               case BVHTREE_FROM_EM_VERTS:
+               case BVHTREE_FROM_EM_EDGES:
+               case BVHTREE_FROM_EM_LOOPTRI:
+                       BLI_assert(false);
+                       break;
        }
 
        if (data_cp.tree != NULL) {
index e19320fa220cd6742f99f7451d05a273f05c15c9..b826e72acaf7ae319e7741ec043971ce6dfc3d49 100644 (file)
@@ -111,6 +111,10 @@ typedef struct SnapObjectData_EditMesh {
        SnapObjectData sd;
        BVHTreeFromEditMesh *bvh_trees[3];
 
+        /* It's like a boundbox. It is tested first to avoid
+         * to create a bvhtree for all the edited objects. */
+       float min[3], max[3];
+
 } SnapObjectData_EditMesh;
 
 struct SnapObjectContext {
@@ -156,6 +160,19 @@ struct SnapObjectContext {
 
 typedef void(*IterSnapObjsCallback)(SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data);
 
+static void min_max_from_bmesh(
+        BMesh *bm, float r_min[3], float r_max[3])
+{
+       BMIter iter;
+       BMVert *eve;
+
+       INIT_MINMAX(r_min, r_max);
+       BM_ITER_MESH(eve, &iter, bm, BM_VERTS_OF_MESH) {
+               minmax_v3v3_v3(r_min, r_max, eve->co);
+       }
+}
+
+
 /**
  * Walks through all objects in the scene to create the list of objets to snap.
  *
@@ -170,8 +187,8 @@ static void iter_snap_objects(
         void *data)
 {
        ViewLayer *view_layer = DEG_get_evaluated_view_layer(sctx->depsgraph);
-       Object *obedit = params->use_object_edit_cage ? OBEDIT_FROM_VIEW_LAYER(view_layer) : NULL;
        const eSnapSelect snap_select = params->snap_select;
+       const bool use_object_edit_cage = params->use_object_edit_cage;
 
        Base *base_act = view_layer->basact;
        for (Base *base = view_layer->object_bases.first; base != NULL; base = base->next) {
@@ -179,20 +196,17 @@ static void iter_snap_objects(
                    !((snap_select == SNAP_NOT_SELECTED && ((base->flag & BASE_SELECTED) || (base->flag_legacy & BA_WAS_SEL))) ||
                      (snap_select == SNAP_NOT_ACTIVE && base == base_act)))
                {
-                       bool use_obedit;
                        Object *obj = base->object;
                        if (obj->transflag & OB_DUPLI) {
                                DupliObject *dupli_ob;
                                ListBase *lb = object_duplilist(sctx->depsgraph, sctx->scene, obj);
                                for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
-                                       use_obedit = obedit && dupli_ob->ob->data == obedit->data;
-                                       sob_callback(sctx, use_obedit, use_obedit ? obedit : dupli_ob->ob, dupli_ob->mat, data);
+                                       sob_callback(sctx, use_object_edit_cage, dupli_ob->ob, dupli_ob->mat, data);
                                }
                                free_object_duplilist(lb);
                        }
 
-                       use_obedit = obedit && obj->data == obedit->data;
-                       sob_callback(sctx, use_obedit, use_obedit ? obedit : obj, obj->obmat, data);
+                       sob_callback(sctx, use_object_edit_cage, obj, obj->obmat, data);
                }
        }
 }
@@ -378,7 +392,7 @@ static bool raycastMesh(
 
        BVHTreeFromMesh *treedata = &sod->treedata;
 
-       /* The tree is owned by the DM and may have been freed since we last used. */
+       /* The tree is owned by the Mesh and may have been freed since we last used. */
        if (treedata->tree) {
                BLI_assert(treedata->cached);
                if (!bvhcache_has_tree(me->runtime.bvh_cache, treedata->tree)) {
@@ -502,14 +516,30 @@ static bool raycastEditMesh(
 
        SnapObjectData_EditMesh *sod = NULL;
        BVHTreeFromEditMesh *treedata = NULL;
+       Object *em_ob = em->ob;
 
        void **sod_p;
-       if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
+       /* Use `em->ob` as the key in ghash since the editmesh is used
+        * to create bvhtree and is the same for each linked object. */
+       if (BLI_ghash_ensure_p(sctx->cache.object_map, em_ob, &sod_p)) {
                sod = *sod_p;
        }
        else {
                sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
                sod->sd.type = SNAP_EDIT_MESH;
+               min_max_from_bmesh(em->bm, sod->min, sod->max);
+       }
+
+       {
+               float min[3], max[3];
+               mul_v3_m4v3(min, obmat, sod->min);
+               mul_v3_m4v3(max, obmat, sod->max);
+
+               if (!isect_ray_aabb_v3_simple(
+                       ray_start, ray_dir, min, max, NULL, NULL))
+               {
+                       return retval;
+               }
        }
 
        if (sod->bvh_trees[2] == NULL) {
@@ -517,7 +547,17 @@ static bool raycastEditMesh(
        }
        treedata = sod->bvh_trees[2];
 
+       BVHCache *em_bvh_cache = ((Mesh *)em_ob->data)->runtime.bvh_cache;
+
+       if (sctx->callbacks.edit_mesh.test_face_fn == NULL) {
+               /* The tree is owned by the Mesh and may have been freed since we last used! */
+               if (!bvhcache_has_tree(em_bvh_cache, treedata->tree)) {
+                       free_bvhtree_from_editmesh(treedata);
+               }
+       }
+
        if (treedata->tree == NULL) {
+               BVHCache **bvh_cache = NULL;
                BLI_bitmap *elem_mask = NULL;
                int looptri_num_active = -1;
 
@@ -527,7 +567,15 @@ static bool raycastEditMesh(
                                em->bm, elem_mask,
                                sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
                }
-               bvhtree_from_editmesh_looptri_ex(treedata, em, elem_mask, looptri_num_active, 0.0f, 4, 6, NULL);
+               else {
+                       /* Only cache if bvhtree is created without a mask.
+                        * This helps keep a standardized bvhtree in cache. */
+                       bvh_cache = &em_bvh_cache;
+               }
+
+               bvhtree_from_editmesh_looptri_ex(
+                       treedata, em, elem_mask, looptri_num_active,
+                       0.0f, 4, 6, bvh_cache);
 
                if (elem_mask) {
                        MEM_freeN(elem_mask);
@@ -669,7 +717,7 @@ static bool raycastObj(
 
        switch (ob->type) {
                case OB_MESH:
-                       if (use_obedit) {
+                       if (use_obedit && BKE_object_is_in_editmode(ob)) {
                                BMEditMesh *em = BKE_editmesh_from_object(ob);
                                retval = raycastEditMesh(
                                        sctx,
@@ -718,7 +766,7 @@ struct RaycastObjUserData {
        bool ret;
 };
 
-static void raycast_obj_cb(SnapObjectContext *sctx, bool is_obedit, Object *ob, float obmat[4][4], void *data)
+static void raycast_obj_cb(SnapObjectContext *sctx, bool use_obedit, Object *ob, float obmat[4][4], void *data)
 {
        struct RaycastObjUserData *dt = data;
 
@@ -726,7 +774,7 @@ static void raycast_obj_cb(SnapObjectContext *sctx, bool is_obedit, Object *ob,
                sctx,
                dt->ray_start, dt->ray_dir,
                ob, obmat, dt->ob_index++,
-               is_obedit, dt->use_occlusion_test,
+               use_obedit, dt->use_occlusion_test,
                dt->ray_depth,
                dt->r_loc, dt->r_no, dt->r_index,
                dt->r_ob, dt->r_obmat,
@@ -1118,6 +1166,13 @@ static short snap_mesh_polygon(
        };
 
        SnapObjectData *sod = BLI_ghash_lookup(sctx->cache.object_map, ob);
+       if (sod == NULL) {
+               /* The object is in edit mode, and the key used
+                * was the object referenced in BMEditMesh */
+               BMEditMesh *em = BKE_editmesh_from_object(ob);
+               sod = BLI_ghash_lookup(sctx->cache.object_map, em->ob);
+       }
+
        BLI_assert(sod != NULL);
 
        if (sod->type == SNAP_MESH) {
@@ -1335,6 +1390,8 @@ static short snapArmature(
        dist_squared_to_projected_aabb_precalc(
                &neasrest_precalc, lpmat, snapdata->win_size, snapdata->mval);
 
+       use_obedit = use_obedit && BKE_object_is_in_editmode(ob);
+
        if (use_obedit == false) {
                /* Test BoundBox */
                BoundBox *bb = BKE_armature_boundbox_get(ob);
@@ -1469,6 +1526,8 @@ static short snapCurve(
        dist_squared_to_projected_aabb_precalc(
                &neasrest_precalc, lpmat, snapdata->win_size, snapdata->mval);
 
+       use_obedit = use_obedit && BKE_object_is_in_editmode(ob);
+
        if (use_obedit == false) {
                /* Test BoundBox */
                BoundBox *bb = BKE_curve_boundbox_get(ob);
@@ -1792,7 +1851,7 @@ static short snapMesh(
        treedata = &sod->treedata;
        bvhtree = sod->bvhtree;
 
-       /* the tree is owned by the DM and may have been freed since we last used! */
+       /* The tree is owned by the Mesh and may have been freed since we last used! */
        if ((sod->has_looptris   && treedata->tree && !bvhcache_has_tree(me->runtime.bvh_cache, treedata->tree)) ||
            (sod->has_loose_edge && bvhtree[0]     && !bvhcache_has_tree(me->runtime.bvh_cache, bvhtree[0]))     ||
            (sod->has_loose_vert && bvhtree[1]     && !bvhcache_has_tree(me->runtime.bvh_cache, bvhtree[1])))
@@ -1982,21 +2041,56 @@ static short snapEditMesh(
 
        SnapObjectData_EditMesh *sod = NULL;
        BVHTreeFromEditMesh *treedata_vert = NULL, *treedata_edge = NULL;
+       Object *em_ob = em->ob;
 
        void **sod_p;
-       if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
+       /* Use `em->ob` as the key in ghash since the editmesh is used
+        * to create bvhtree and is the same for each linked object. */
+       if (BLI_ghash_ensure_p(sctx->cache.object_map, em_ob, &sod_p)) {
                sod = *sod_p;
        }
        else {
                sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
                sod->sd.type = SNAP_EDIT_MESH;
+               min_max_from_bmesh(em->bm, sod->min, sod->max);
        }
 
+       float dist_px_sq = SQUARE(*dist_px);
+
+       {
+               float min[3], max[3];
+               mul_v3_m4v3(min, obmat, sod->min);
+               mul_v3_m4v3(max, obmat, sod->max);
+
+               /* In vertex and edges you need to get the pixel distance from ray to BoundBox, see: T46099, T46816 */
+               struct DistProjectedAABBPrecalc data_precalc;
+               dist_squared_to_projected_aabb_precalc(
+                       &data_precalc, snapdata->pmat, snapdata->win_size, snapdata->mval);
+
+               bool dummy[3];
+               float bb_dist_px_sq = dist_squared_to_projected_aabb(
+                       &data_precalc, min, max, dummy);
+
+               if (bb_dist_px_sq > dist_px_sq) {
+                       return 0;
+               }
+       }
+
+       BVHCache *em_bvh_cache = ((Mesh *)em_ob->data)->runtime.bvh_cache;
+
        if (snapdata->snap_to_flag & SCE_SNAP_MODE_VERTEX) {
                if (sod->bvh_trees[0] == NULL) {
                        sod->bvh_trees[0] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(**sod->bvh_trees));
                }
                treedata_vert = sod->bvh_trees[0];
+
+               if (sctx->callbacks.edit_mesh.test_vert_fn == NULL) {
+                       /* The tree is owned by the Mesh and may have been freed since we last used! */
+                       if (!bvhcache_has_tree(em_bvh_cache, treedata_vert->tree)) {
+                               free_bvhtree_from_editmesh(treedata_vert);
+                       }
+               }
+
                if (treedata_vert->tree == NULL) {
                        BLI_bitmap *verts_mask = NULL;
                        int verts_num_active = -1;
@@ -2006,9 +2100,13 @@ static short snapEditMesh(
                                        BM_VERTS_OF_MESH, em->bm, verts_mask,
                                        (bool(*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_vert_fn,
                                        sctx->callbacks.edit_mesh.user_data);
+
+                               bvhtree_from_editmesh_verts_ex(treedata_vert, em, verts_mask, verts_num_active, 0.0f, 2, 6);
+                               MEM_freeN(verts_mask);
+                       }
+                       else {
+                               bvhtree_from_editmesh_verts(treedata_vert, em, 0.0f, 2, 6, &em_bvh_cache);
                        }
-                       bvhtree_from_editmesh_verts_ex(treedata_vert, em, verts_mask, verts_num_active, 0.0f, 2, 6);
-                       MEM_SAFE_FREE(verts_mask);
                }
        }
 
@@ -2017,6 +2115,14 @@ static short snapEditMesh(
                        sod->bvh_trees[1] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(**sod->bvh_trees));
                }
                treedata_edge = sod->bvh_trees[1];
+
+               if (sctx->callbacks.edit_mesh.test_edge_fn == NULL) {
+                       /* The tree is owned by the Mesh and may have been freed since we last used! */
+                       if (!bvhcache_has_tree(em_bvh_cache, treedata_edge->tree)) {
+                               free_bvhtree_from_editmesh(treedata_edge);
+                       }
+               }
+
                if (treedata_edge->tree == NULL) {
                        BLI_bitmap *edges_mask = NULL;
                        int edges_num_active = -1;
@@ -2027,9 +2133,12 @@ static short snapEditMesh(
                                        (bool(*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_edge_fn,
                                        sctx->callbacks.edit_mesh.user_data);
 
+                               bvhtree_from_editmesh_edges_ex(treedata_edge, em, edges_mask, edges_num_active, 0.0f, 2, 6);
+                               MEM_freeN(edges_mask);
+                       }
+                       else {
+                               bvhtree_from_editmesh_edges(treedata_edge, em, 0.0f, 2, 6, &em_bvh_cache);
                        }
-                       bvhtree_from_editmesh_edges_ex(treedata_edge, em, edges_mask, edges_num_active, 0.0f, 2, 6);
-                       MEM_SAFE_FREE(edges_mask);
                }
        }
 
@@ -2043,7 +2152,7 @@ static short snapEditMesh(
 
        BVHTreeNearest nearest = {
                .index = -1,
-               .dist_sq = SQUARE(*dist_px),
+               .dist_sq = dist_px_sq,
        };
        int last_index = nearest.index;
        short elem = SCE_SNAP_MODE_VERTEX;
@@ -2119,7 +2228,7 @@ static short snapObject(
 
        switch (ob->type) {
                case OB_MESH:
-                       if (use_obedit) {
+                       if (use_obedit && BKE_object_is_in_editmode(ob)) {
                                BMEditMesh *em = BKE_editmesh_from_object(ob);
                                retval = snapEditMesh(
                                        sctx, snapdata, ob, em, obmat,