diff options
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/BKE_bvhutils.h | 44 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/bvhutils.c | 276 | ||||
-rw-r--r-- | source/blender/editors/transform/transform_snap_object.c | 32 |
3 files changed, 216 insertions, 136 deletions
diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h index d010f5dd836..a2d45625f42 100644 --- a/source/blender/blenkernel/BKE_bvhutils.h +++ b/source/blender/blenkernel/BKE_bvhutils.h @@ -93,19 +93,18 @@ typedef struct BVHTreeFromMesh { * * free_bvhtree_from_mesh should be called when the tree is no longer needed. */ -BVHTree *bvhtree_from_editmesh_verts(BVHTreeFromEditMesh *data, - struct BMEditMesh *em, - float epsilon, - int tree_type, - int axis, - BVHCache **bvh_cache); +BVHTree *bvhtree_from_editmesh_verts( + BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis); + BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data, struct BMEditMesh *em, const BLI_bitmap *mask, int verts_num_active, float epsilon, int tree_type, - int axis); + int axis, + const int bvh_cache_type, + BVHCache **bvh_cache); BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data, const struct MVert *vert, @@ -119,19 +118,18 @@ BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data, const int bvh_cache_type, BVHCache **bvh_cache); -BVHTree *bvhtree_from_editmesh_edges(BVHTreeFromEditMesh *data, - struct BMEditMesh *em, - float epsilon, - int tree_type, - int axis, - BVHCache **bvh_cache); +BVHTree *bvhtree_from_editmesh_edges( + BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis); + BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data, struct BMEditMesh *em, const BLI_bitmap *edges_mask, int edges_num_active, float epsilon, int tree_type, - int axis); + int axis, + const int bvh_cache_type, + BVHCache **bvh_cache); BVHTree *bvhtree_from_mesh_edges_ex(struct BVHTreeFromMesh *data, const struct MVert *vert, @@ -161,12 +159,9 @@ BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data, const int bvh_cache_type, BVHCache **bvh_cache); -BVHTree *bvhtree_from_editmesh_looptri(BVHTreeFromEditMesh *data, - struct BMEditMesh *em, - float epsilon, - int tree_type, - int axis, - BVHCache **bvhCache); +BVHTree *bvhtree_from_editmesh_looptri( + BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis); + BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data, struct BMEditMesh *em, const BLI_bitmap *mask, @@ -174,7 +169,8 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data, float epsilon, int tree_type, int axis, - BVHCache **bvhCache); + const int bvh_cache_type, + BVHCache **bvh_cache); BVHTree *bvhtree_from_mesh_looptri_ex(struct BVHTreeFromMesh *data, const struct MVert *vert, @@ -197,6 +193,12 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data, const int type, const int tree_type); +BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data, + struct BMEditMesh *em, + const int tree_type, + const int bvh_cache_type, + BVHCache **bvh_cache); + /** * Frees data allocated by a call to bvhtree_from_mesh_*. */ diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c index 1210e6f18ce..04e3b4ff2ae 100644 --- a/source/blender/blenkernel/intern/bvhutils.c +++ b/source/blender/blenkernel/intern/bvhutils.c @@ -425,11 +425,11 @@ static BVHTree *bvhtree_from_editmesh_verts_create_tree(float epsilon, int tree_type, int axis, BMEditMesh *em, - const int verts_num, const BLI_bitmap *verts_mask, int verts_num_active) { BM_mesh_elem_table_ensure(em->bm, BM_VERT); + const int verts_num = em->bm->totvert; if (verts_mask) { BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num)); } @@ -516,53 +516,53 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data, int verts_num_active, float epsilon, int tree_type, - int axis) + int axis, + const int bvh_cache_type, + BVHCache **bvh_cache) { - BVHTree *tree = bvhtree_from_editmesh_verts_create_tree( - epsilon, tree_type, axis, em, em->bm->totvert, verts_mask, verts_num_active); - - if (tree) { - memset(data, 0, sizeof(*data)); - data->tree = tree; - data->em = em; - data->nearest_callback = NULL; - data->raycast_callback = editmesh_verts_spherecast; - } - - return tree; -} + BVHTree *tree = NULL; -BVHTree *bvhtree_from_editmesh_verts(BVHTreeFromEditMesh *data, - BMEditMesh *em, - float epsilon, - int tree_type, - int axis, - BVHCache **bvh_cache) -{ if (bvh_cache) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree); + data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &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); + data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &data->tree); if (data->cached == false) { - data->tree = bvhtree_from_editmesh_verts_ex(data, em, NULL, -1, epsilon, tree_type, axis); + tree = bvhtree_from_editmesh_verts_create_tree( + epsilon, tree_type, axis, em, verts_mask, verts_num_active); /* Save on cache for later use */ /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(bvh_cache, data->tree, BVHTREE_FROM_EM_VERTS); + bvhcache_insert(bvh_cache, tree, bvh_cache_type); data->cached = true; } BLI_rw_mutex_unlock(&cache_rwlock); } } else { - data->tree = bvhtree_from_editmesh_verts_ex(data, em, NULL, -1, epsilon, tree_type, axis); + tree = bvhtree_from_editmesh_verts_create_tree( + epsilon, tree_type, axis, em, verts_mask, verts_num_active); + } + + if (tree) { + memset(data, 0, sizeof(*data)); + data->tree = tree; + data->em = em; + data->nearest_callback = NULL; + data->raycast_callback = editmesh_verts_spherecast; + data->cached = bvh_cache != NULL; } - return data->tree; + return tree; +} + +BVHTree *bvhtree_from_editmesh_verts( + BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis) +{ + return bvhtree_from_editmesh_verts_ex(data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL); } /** @@ -628,11 +628,12 @@ static BVHTree *bvhtree_from_editmesh_edges_create_tree(float epsilon, int tree_type, int axis, BMEditMesh *em, - const int edges_num, const BLI_bitmap *edges_mask, int edges_num_active) { BM_mesh_elem_table_ensure(em->bm, BM_EDGE); + const int edges_num = em->bm->totedge; + if (edges_mask) { BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edges_num)); } @@ -732,55 +733,53 @@ BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data, int edges_num_active, float epsilon, int tree_type, - int axis) + int axis, + const int bvh_cache_type, + BVHCache **bvh_cache) { - int edge_num = em->bm->totedge; - - BVHTree *tree = bvhtree_from_editmesh_edges_create_tree( - epsilon, tree_type, axis, em, edge_num, edges_mask, edges_num_active); - - if (tree) { - memset(data, 0, sizeof(*data)); - data->tree = tree; - data->em = em; - data->nearest_callback = NULL; /* TODO */ - data->raycast_callback = NULL; /* TODO */ - } - - return tree; -} + BVHTree *tree = NULL; -BVHTree *bvhtree_from_editmesh_edges(BVHTreeFromEditMesh *data, - BMEditMesh *em, - float epsilon, - int tree_type, - int axis, - BVHCache **bvh_cache) -{ if (bvh_cache) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree); + data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &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); + data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &data->tree); if (data->cached == false) { - data->tree = bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis); + tree = bvhtree_from_editmesh_edges_create_tree( + epsilon, tree_type, axis, em, edges_mask, edges_num_active); /* Save on cache for later use */ /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(bvh_cache, data->tree, BVHTREE_FROM_EM_EDGES); + bvhcache_insert(bvh_cache, tree, bvh_cache_type); data->cached = true; } BLI_rw_mutex_unlock(&cache_rwlock); } } else { - data->tree = bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis); + tree = bvhtree_from_editmesh_edges_create_tree( + epsilon, tree_type, axis, em, edges_mask, edges_num_active); + } + + if (tree) { + memset(data, 0, sizeof(*data)); + data->tree = tree; + data->em = em; + data->nearest_callback = NULL; /* TODO */ + data->raycast_callback = NULL; /* TODO */ + data->cached = bvh_cache != NULL; } - return data->tree; + return tree; +} + +BVHTree *bvhtree_from_editmesh_edges( + BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis) +{ + return bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL); } /** @@ -985,12 +984,11 @@ static BVHTree *bvhtree_from_editmesh_looptri_create_tree(float epsilon, int tree_type, int axis, BMEditMesh *em, - const int looptri_num, const BLI_bitmap *looptri_mask, int looptri_num_active) { BVHTree *tree = NULL; - int i; + const int looptri_num = em->tottri; if (looptri_num) { if (looptri_mask) { @@ -1004,26 +1002,24 @@ static BVHTree *bvhtree_from_editmesh_looptri_create_tree(float epsilon, /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */ tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis); if (tree) { - if (em) { - const struct BMLoop *(*looptris)[3] = (void *)em->looptris; - - /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden - * and/or selected. Even if the faces themselves are not selected for the snapped - * transform, having a vertex selected means the face (and thus it's tessellated - * triangles) will be moving and will not be a good snap targets. */ - for (i = 0; i < looptri_num; i++) { - const BMLoop **ltri = looptris[i]; - bool insert = looptri_mask ? BLI_BITMAP_TEST_BOOL(looptri_mask, i) : true; - - if (insert) { - /* No reason found to block hit-testing the triangle for snap, so insert it now.*/ - float co[3][3]; - copy_v3_v3(co[0], ltri[0]->v->co); - copy_v3_v3(co[1], ltri[1]->v->co); - copy_v3_v3(co[2], ltri[2]->v->co); - - BLI_bvhtree_insert(tree, i, co[0], 3); - } + const struct BMLoop *(*looptris)[3] = (void *)em->looptris; + + /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden + * and/or selected. Even if the faces themselves are not selected for the snapped + * transform, having a vertex selected means the face (and thus it's tessellated + * triangles) will be moving and will not be a good snap targets. */ + for (int i = 0; i < looptri_num; i++) { + const BMLoop **ltri = looptris[i]; + bool insert = looptri_mask ? BLI_BITMAP_TEST_BOOL(looptri_mask, i) : true; + + if (insert) { + /* No reason found to block hit-testing the triangle for snap, so insert it now.*/ + float co[3][3]; + copy_v3_v3(co[0], ltri[0]->v->co); + copy_v3_v3(co[1], ltri[1]->v->co); + copy_v3_v3(co[2], ltri[2]->v->co); + + BLI_bvhtree_insert(tree, i, co[0], 3); } } BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active); @@ -1116,33 +1112,34 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data, float epsilon, int tree_type, int axis, - BVHCache **bvhCache) + const int bvh_cache_type, + BVHCache **bvh_cache) { /* BMESH specific check that we have tessfaces, * we _could_ tessellate here but rather not - campbell */ BVHTree *tree = NULL; - if (bvhCache) { + if (bvh_cache) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - bool in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree); + bool in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree); BLI_rw_mutex_unlock(&cache_rwlock); if (in_cache == false) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree); + in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree); if (in_cache == false) { tree = bvhtree_from_editmesh_looptri_create_tree( - epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active); + epsilon, tree_type, axis, em, looptri_mask, looptri_num_active); /* Save on cache for later use */ /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(bvhCache, tree, BVHTREE_FROM_EM_LOOPTRI); + bvhcache_insert(bvh_cache, tree, bvh_cache_type); } BLI_rw_mutex_unlock(&cache_rwlock); } } else { tree = bvhtree_from_editmesh_looptri_create_tree( - epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active); + epsilon, tree_type, axis, em, looptri_mask, looptri_num_active); } if (tree) { @@ -1150,19 +1147,15 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data, data->nearest_callback = editmesh_looptri_nearest_point; data->raycast_callback = editmesh_looptri_spherecast; data->em = em; - data->cached = bvhCache != NULL; + data->cached = bvh_cache != NULL; } return tree; } -BVHTree *bvhtree_from_editmesh_looptri(BVHTreeFromEditMesh *data, - BMEditMesh *em, - float epsilon, - int tree_type, - int axis, - BVHCache **bvhCache) +BVHTree *bvhtree_from_editmesh_looptri( + BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis) { - return bvhtree_from_editmesh_looptri_ex(data, em, NULL, -1, epsilon, tree_type, axis, bvhCache); + return bvhtree_from_editmesh_looptri_ex(data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL); } /** @@ -1493,6 +1486,97 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data, return tree; } +/** + * Builds or queries a bvhcache for the cache bvhtree of the request type. + */ +BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data, + struct BMEditMesh *em, + const int tree_type, + const int bvh_cache_type, + BVHCache **bvh_cache) +{ + BVHTree *tree = NULL; + bool is_cached = false; + + memset(data, 0, sizeof(*data)); + + if (bvh_cache) { + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); + bool is_cached = bvhcache_find(*bvh_cache, bvh_cache_type, &tree); + BLI_rw_mutex_unlock(&cache_rwlock); + + if (is_cached && tree == NULL) { + return tree; + } + } + data->tree = tree; + data->em = em; + data->cached = is_cached; + + switch (bvh_cache_type) { + case BVHTREE_FROM_EM_VERTS: + if (is_cached == false) { + tree = bvhtree_from_editmesh_verts_ex( + data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache); + } + else { + data->nearest_callback = NULL; + data->raycast_callback = editmesh_verts_spherecast; + } + break; + + case BVHTREE_FROM_EM_EDGES: + if (is_cached == false) { + tree = bvhtree_from_editmesh_edges_ex( + data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache); + } + else { + /* Setup BVHTreeFromMesh */ + data->nearest_callback = NULL; /* TODO */ + data->raycast_callback = NULL; /* TODO */ + } + break; + + case BVHTREE_FROM_EM_LOOPTRI: + if (is_cached == false) { + tree = bvhtree_from_editmesh_looptri_ex( + data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache); + } + else { + /* Setup BVHTreeFromMesh */ + data->nearest_callback = editmesh_looptri_nearest_point; + data->raycast_callback = editmesh_looptri_spherecast; + } + break; + case BVHTREE_FROM_VERTS: + case BVHTREE_FROM_EDGES: + case BVHTREE_FROM_FACES: + case BVHTREE_FROM_LOOPTRI: + case BVHTREE_FROM_LOOPTRI_NO_HIDDEN: + case BVHTREE_FROM_LOOSEVERTS: + case BVHTREE_FROM_LOOSEEDGES: + BLI_assert(false); + break; + } + + if (data->tree != NULL) { +#ifdef DEBUG + if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) { + printf("tree_type %d obtained instead of %d\n", + BLI_bvhtree_get_tree_type(data->tree), + tree_type); + } +#endif + BLI_assert(data->cached); + } + else { + free_bvhtree_from_editmesh(data); + memset(data, 0, sizeof(*data)); + } + + return tree; +} + /** \} */ /* Frees data allocated by a call to bvhtree_from_editmesh_*. */ @@ -1581,7 +1665,7 @@ void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type) { BVHCacheItem *item = NULL; - assert(bvhcache_find(*cache_p, type, &(BVHTree *){0}) == false); + assert(tree && bvhcache_find(*cache_p, type, &(BVHTree *){0}) == false); item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem"); diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c index 7818f20060f..132d2511065 100644 --- a/source/blender/editors/transform/transform_snap_object.c +++ b/source/blender/editors/transform/transform_snap_object.c @@ -583,37 +583,31 @@ static bool raycastEditMesh(SnapObjectContext *sctx, } if (treedata->tree == NULL) { - BVHCache **bvh_cache = NULL; - BLI_bitmap *elem_mask = NULL; - BMEditMesh *em_orig; - int looptri_num_active = -1; - /* Get original version of the edit_mesh. */ - em_orig = BKE_editmesh_from_object(DEG_get_original_object(ob)); + BMEditMesh *em_orig = BKE_editmesh_from_object(DEG_get_original_object(ob)); if (sctx->callbacks.edit_mesh.test_face_fn) { BMesh *bm = em_orig->bm; BLI_assert(poly_to_tri_count(bm->totface, bm->totloop) == em_orig->tottri); - elem_mask = BLI_BITMAP_NEW(em_orig->tottri, __func__); - looptri_num_active = BM_iter_mesh_bitmap_from_filter_tessface( + BLI_bitmap *elem_mask = BLI_BITMAP_NEW(em_orig->tottri, __func__); + int looptri_num_active = BM_iter_mesh_bitmap_from_filter_tessface( bm, elem_mask, sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data); + + bvhtree_from_editmesh_looptri_ex( + treedata, em_orig, elem_mask, looptri_num_active, 0.0f, 4, 6, 0, NULL); + + MEM_freeN(elem_mask); } else { /* Only cache if bvhtree is created without a mask. * This helps keep a standardized bvhtree in cache. */ - bvh_cache = em_bvh_cache; + BKE_bvhtree_from_editmesh_get(treedata, em_orig, 4, BVHTREE_FROM_EM_LOOPTRI, em_bvh_cache); } - bvhtree_from_editmesh_looptri_ex( - treedata, em_orig, elem_mask, looptri_num_active, 0.0f, 4, 6, bvh_cache); - - if (elem_mask) { - MEM_freeN(elem_mask); - } if (treedata->tree == NULL) { return retval; } @@ -2284,11 +2278,11 @@ static short snapEditMesh(SnapObjectContext *sctx, sctx->callbacks.edit_mesh.user_data); bvhtree_from_editmesh_verts_ex( - treedata_vert, em, verts_mask, verts_num_active, 0.0f, 2, 6); + treedata_vert, em, verts_mask, verts_num_active, 0.0f, 2, 6, 0, NULL); MEM_freeN(verts_mask); } else { - bvhtree_from_editmesh_verts(treedata_vert, em, 0.0f, 2, 6, em_bvh_cache); + BKE_bvhtree_from_editmesh_get(treedata_vert, em, 2, BVHTREE_FROM_EM_VERTS, em_bvh_cache); } } } @@ -2320,11 +2314,11 @@ static short snapEditMesh(SnapObjectContext *sctx, sctx->callbacks.edit_mesh.user_data); bvhtree_from_editmesh_edges_ex( - treedata_edge, em, edges_mask, edges_num_active, 0.0f, 2, 6); + treedata_edge, em, edges_mask, edges_num_active, 0.0f, 2, 6, 0, NULL); MEM_freeN(edges_mask); } else { - bvhtree_from_editmesh_edges(treedata_edge, em, 0.0f, 2, 6, em_bvh_cache); + BKE_bvhtree_from_editmesh_get(treedata_vert, em, 2, BVHTREE_FROM_EM_EDGES, em_bvh_cache); } } } |