From 59286ddcf80c391094d64dcbbb94640bf73bd0d9 Mon Sep 17 00:00:00 2001 From: Germano Date: Mon, 23 Jul 2018 11:04:58 -0300 Subject: transform_snap_object: Better bvhtree creation management for editing multiple objects. - 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 | 8 +- source/blender/blenkernel/intern/bvhutils.c | 79 +++++++++-- .../editors/transform/transform_snap_object.c | 149 ++++++++++++++++++--- 3 files changed, 203 insertions(+), 33 deletions(-) (limited to 'source') diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h index d79a7eae53e..a0780a5be54 100644 --- a/source/blender/blenkernel/BKE_bvhutils.h +++ b/source/blender/blenkernel/BKE_bvhutils.h @@ -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, }; diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c index 1a7c4e2a4a0..19ac81b4bb7 100644 --- a/source/blender/blenkernel/intern/bvhutils.c +++ b/source/blender/blenkernel/intern/bvhutils.c @@ -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) { diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c index e19320fa220..b826e72acaf 100644 --- a/source/blender/editors/transform/transform_snap_object.c +++ b/source/blender/editors/transform/transform_snap_object.c @@ -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, -- cgit v1.2.3