diff options
Diffstat (limited to 'source/blender/blenkernel/intern/bvhutils.c')
| -rw-r--r-- | source/blender/blenkernel/intern/bvhutils.c | 446 |
1 files changed, 353 insertions, 93 deletions
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c index c678f71dff9..1a7c4e2a4a0 100644 --- a/source/blender/blenkernel/intern/bvhutils.c +++ b/source/blender/blenkernel/intern/bvhutils.c @@ -34,6 +34,7 @@ #include <math.h> #include <assert.h> +#include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" #include "BLI_utildefines.h" @@ -43,6 +44,8 @@ #include "BKE_DerivedMesh.h" #include "BKE_editmesh.h" +#include "BKE_mesh.h" +#include "BKE_mesh_runtime.h" #include "MEM_guardedalloc.h" @@ -423,7 +426,8 @@ static BVHTree *bvhtree_from_mesh_verts_create_tree( const MVert *vert, const int verts_num, const BLI_bitmap *verts_mask, int verts_num_active) { - BLI_assert(vert != NULL); + BVHTree *tree = NULL; + if (verts_mask) { BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num)); } @@ -431,17 +435,19 @@ static BVHTree *bvhtree_from_mesh_verts_create_tree( verts_num_active = verts_num; } - BVHTree *tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis); + if (verts_num_active) { + tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis); - if (tree) { - for (int i = 0; i < verts_num; i++) { - if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) { - continue; + if (tree) { + for (int i = 0; i < verts_num; i++) { + if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) { + continue; + } + BLI_bvhtree_insert(tree, i, vert[i].co, 1); } - BLI_bvhtree_insert(tree, i, vert[i].co, 1); + BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active); + BLI_bvhtree_balance(tree); } - BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active); - BLI_bvhtree_balance(tree); } return tree; @@ -567,29 +573,31 @@ static BVHTree *bvhtree_from_mesh_edges_create_tree( const BLI_bitmap *edges_mask, int edges_num_active, float epsilon, int tree_type, int axis) { + BVHTree *tree = NULL; + if (edges_mask) { BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edge_num)); } else { edges_num_active = edge_num; } - BLI_assert(vert != NULL); - BLI_assert(edge != NULL); - /* Create a bvh-tree of the given target */ - BVHTree *tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis); - if (tree) { - for (int i = 0; i < edge_num; i++) { - if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) { - continue; - } - float co[2][3]; - copy_v3_v3(co[0], vert[edge[i].v1].co); - copy_v3_v3(co[1], vert[edge[i].v2].co); + if (edges_num_active) { + /* Create a bvh-tree of the given target */ + tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis); + if (tree) { + for (int i = 0; i < edge_num; i++) { + if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) { + continue; + } + float co[2][3]; + copy_v3_v3(co[0], vert[edge[i].v1].co); + copy_v3_v3(co[1], vert[edge[i].v2].co); - BLI_bvhtree_insert(tree, i, co[0], 2); + BLI_bvhtree_insert(tree, i, co[0], 2); + } + BLI_bvhtree_balance(tree); } - BLI_bvhtree_balance(tree); } return tree; @@ -833,22 +841,21 @@ static BVHTree *bvhtree_from_mesh_looptri_create_tree( const BLI_bitmap *looptri_mask, int looptri_num_active) { BVHTree *tree = NULL; - int i; - if (looptri_num) { - if (looptri_mask) { - BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num)); - } - else { - looptri_num_active = looptri_num; - } + if (looptri_mask) { + BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num)); + } + else { + looptri_num_active = looptri_num; + } + if (looptri_num_active) { /* Create a bvh-tree of the given target */ /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */ tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis); if (tree) { if (vert && looptri) { - for (i = 0; i < looptri_num; i++) { + for (int i = 0; i < looptri_num; i++) { float co[3][3]; if (looptri_mask && !BLI_BITMAP_TEST_BOOL(looptri_mask, i)) { continue; @@ -902,23 +909,23 @@ BVHTree *bvhtree_from_editmesh_looptri_ex( /* BMESH specific check that we have tessfaces, * we _could_ tessellate here but rather not - campbell */ - BVHTree *tree; + BVHTree *tree = NULL; if (bvhCache) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - tree = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI); + bool in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree); BLI_rw_mutex_unlock(&cache_rwlock); - if (tree == NULL) { + if (in_cache == false) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI); - if (tree == NULL) { + in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree); + if (in_cache == false) { tree = bvhtree_from_editmesh_looptri_create_tree( epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active); - if (tree) { - /* Save on cache for later use */ - /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(bvhCache, tree, BVHTREE_FROM_EM_LOOPTRI); - } + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(bvhCache, tree, BVHTREE_FROM_EM_LOOPTRI); + } BLI_rw_mutex_unlock(&cache_rwlock); } @@ -976,6 +983,55 @@ BVHTree *bvhtree_from_mesh_looptri_ex( return tree; } +static BLI_bitmap *loose_verts_map_get( + const MEdge *medge, int edges_num, + const MVert *UNUSED(mvert), int verts_num, + int *r_loose_vert_num) +{ + BLI_bitmap *loose_verts_mask = BLI_BITMAP_NEW(verts_num, __func__); + BLI_BITMAP_SET_ALL(loose_verts_mask, true, verts_num); + + const MEdge *e = medge; + int num_linked_verts = 0; + for (;edges_num--; e++) { + if (BLI_BITMAP_TEST(loose_verts_mask, e->v1)) { + BLI_BITMAP_DISABLE(loose_verts_mask, e->v1); + num_linked_verts++; + } + if (BLI_BITMAP_TEST(loose_verts_mask, e->v2)) { + BLI_BITMAP_DISABLE(loose_verts_mask, e->v2); + num_linked_verts++; + } + } + + *r_loose_vert_num = verts_num - num_linked_verts; + + return loose_verts_mask; +} + +static BLI_bitmap *loose_edges_map_get( + const MEdge *medge, const int edges_len, + int *r_loose_edge_len) +{ + BLI_bitmap *loose_edges_mask = BLI_BITMAP_NEW(edges_len, __func__); + + int loose_edges_len = 0; + const MEdge *e = medge; + for (int i = 0; i < edges_len; i++, e++) { + if (e->flag & ME_LOOSEEDGE) { + BLI_BITMAP_ENABLE(loose_edges_mask, i); + loose_edges_len++; + } + else { + BLI_BITMAP_DISABLE(loose_edges_mask, i); + } + } + + *r_loose_edge_len = loose_edges_len; + + return loose_edges_mask; +} + /** * Builds or queries a bvhcache for the cache bvhtree of the request type. */ @@ -1000,54 +1056,94 @@ BVHTree *bvhtree_from_mesh_get( bool looptri_allocated = false; BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - tree = bvhcache_find(dm->bvhCache, type); + bool in_cache = bvhcache_find(dm->bvhCache, type, &tree); BLI_rw_mutex_unlock(&cache_rwlock); + if (in_cache && tree == NULL) { + memset(data, 0, sizeof(*data)); + return tree; + } + switch (type) { case BVHTREE_FROM_VERTS: + case BVHTREE_FROM_LOOSEVERTS: raycast_callback = mesh_verts_spherecast; mvert = DM_get_vert_array(dm, &vert_allocated); - if (tree == NULL) { - /* Not in cache */ + if (in_cache == false) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(dm->bvhCache, BVHTREE_FROM_VERTS); - if (tree == NULL) { + in_cache = bvhcache_find(dm->bvhCache, type, &tree); + if (in_cache == false) { + BLI_bitmap *loose_verts_mask = NULL; + int loose_vert_num = -1; + int verts_num = dm->getNumVerts(dm); + + if (type == BVHTREE_FROM_LOOSEVERTS) { + medge = DM_get_edge_array(dm, &edge_allocated); + + loose_verts_mask = loose_verts_map_get( + medge, dm->getNumEdges(dm), mvert, + verts_num, &loose_vert_num); + + if (edge_allocated) { + MEM_freeN(medge); + edge_allocated = false; + } + medge = NULL; + } + tree = bvhtree_from_mesh_verts_create_tree( - 0.0, tree_type, 6, mvert, dm->getNumVerts(dm), NULL, -1); + 0.0, tree_type, 6, mvert, verts_num, + loose_verts_mask, loose_vert_num); - if (tree) { - /* Save on cache for later use */ - /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTS); + if (loose_verts_mask != NULL) { + MEM_freeN(loose_verts_mask); } + + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&dm->bvhCache, tree, type); + } + BLI_rw_mutex_unlock(&cache_rwlock); } break; case BVHTREE_FROM_EDGES: + case BVHTREE_FROM_LOOSEEDGES: nearest_callback = mesh_edges_nearest_point; raycast_callback = mesh_edges_spherecast; mvert = DM_get_vert_array(dm, &vert_allocated); medge = DM_get_edge_array(dm, &edge_allocated); - if (tree == NULL) { - /* Not in cache */ + if (in_cache == false) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(dm->bvhCache, BVHTREE_FROM_EDGES); - if (tree == NULL) { + in_cache = bvhcache_find(dm->bvhCache, type, &tree); + if (in_cache == false) { + BLI_bitmap *loose_edges_mask = NULL; + int loose_edges_num = -1; + int edges_num = dm->getNumEdges(dm); + + if (type == BVHTREE_FROM_LOOSEEDGES) { + loose_edges_mask = loose_edges_map_get( + medge, edges_num, &loose_edges_num); + } + tree = bvhtree_from_mesh_edges_create_tree( - mvert, medge, dm->getNumEdges(dm), - NULL, -1, 0.0, tree_type, 6); + mvert, medge, edges_num, + loose_edges_mask, loose_edges_num, 0.0, tree_type, 6); - if (tree) { - /* Save on cache for later use */ - /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_EDGES); + if (loose_edges_mask != NULL) { + MEM_freeN(loose_edges_mask); } + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&dm->bvhCache, tree, type); } BLI_rw_mutex_unlock(&cache_rwlock); } @@ -1060,22 +1156,19 @@ BVHTree *bvhtree_from_mesh_get( mvert = DM_get_vert_array(dm, &vert_allocated); mface = DM_get_tessface_array(dm, &face_allocated); - if (tree == NULL) { - /* Not in cache */ + if (in_cache == false) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(dm->bvhCache, BVHTREE_FROM_FACES); - if (tree == NULL) { + in_cache = bvhcache_find(dm->bvhCache, BVHTREE_FROM_FACES, &tree); + if (in_cache == false) { int numFaces = dm->getNumTessFaces(dm); BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0)); tree = bvhtree_from_mesh_faces_create_tree( 0.0, tree_type, 6, mvert, mface, numFaces, NULL, -1); - if (tree) { - /* Save on cache for later use */ - /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_FACES); - } + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_FACES); } BLI_rw_mutex_unlock(&cache_rwlock); } @@ -1089,11 +1182,10 @@ BVHTree *bvhtree_from_mesh_get( mloop = DM_get_loop_array(dm, &loop_allocated); looptri = dm->getLoopTriArray(dm); - if (tree == NULL) { - /* Not in cache */ + if (in_cache == false) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(dm->bvhCache, BVHTREE_FROM_LOOPTRI); - if (tree == NULL) { + in_cache = bvhcache_find(dm->bvhCache, BVHTREE_FROM_LOOPTRI, &tree); + if (in_cache == false) { int looptri_num = dm->getNumLoopTri(dm); /* this assert checks we have looptris, @@ -1103,11 +1195,10 @@ BVHTree *bvhtree_from_mesh_get( tree = bvhtree_from_mesh_looptri_create_tree( 0.0, tree_type, 6, mvert, mloop, looptri, looptri_num, NULL, -1); - if (tree) { - /* Save on cache for later use */ - /* printf("BVHTree built and saved on cache\n"); */ - bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_LOOPTRI); - } + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_LOOPTRI); } BLI_rw_mutex_unlock(&cache_rwlock); } @@ -1152,7 +1243,7 @@ BVHTree *bvhtree_from_mesh_get( MEM_freeN(mloop); } if (looptri_allocated) { - MEM_freeN((void*)looptri); + MEM_freeN((void *)looptri); } memset(data, 0, sizeof(*data)); @@ -1161,6 +1252,181 @@ BVHTree *bvhtree_from_mesh_get( return tree; } +/** + * Builds or queries a bvhcache for the cache bvhtree of the request type. + */ +BVHTree *BKE_bvhtree_from_mesh_get( + struct BVHTreeFromMesh *data, struct Mesh *mesh, + const int type, const int tree_type) +{ + struct BVHTreeFromMesh data_cp = {0}; + + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); + data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree); + BLI_rw_mutex_unlock(&cache_rwlock); + + if (data_cp.cached && data_cp.tree == NULL) { + memset(data, 0, sizeof(*data)); + return data_cp.tree; + } + + switch (type) { + case BVHTREE_FROM_VERTS: + case BVHTREE_FROM_LOOSEVERTS: + data_cp.raycast_callback = mesh_verts_spherecast; + + data_cp.vert = mesh->mvert; + + if (data_cp.cached == false) { + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); + data_cp.cached = bvhcache_find( + mesh->runtime.bvh_cache, type, &data_cp.tree); + + if (data_cp.cached == false) { + BLI_bitmap *loose_verts_mask = NULL; + int loose_vert_len = -1; + int verts_len = mesh->totvert; + + if (type == BVHTREE_FROM_LOOSEVERTS) { + loose_verts_mask = loose_verts_map_get( + mesh->medge, mesh->totedge, data_cp.vert, + verts_len, &loose_vert_len); + } + + data_cp.tree = bvhtree_from_mesh_verts_create_tree( + 0.0, tree_type, 6, data_cp.vert, verts_len, + loose_verts_mask, loose_vert_len); + + if (loose_verts_mask != NULL) { + MEM_freeN(loose_verts_mask); + } + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, type); + } + BLI_rw_mutex_unlock(&cache_rwlock); + } + break; + + case BVHTREE_FROM_EDGES: + case BVHTREE_FROM_LOOSEEDGES: + data_cp.nearest_callback = mesh_edges_nearest_point; + data_cp.raycast_callback = mesh_edges_spherecast; + + data_cp.vert = mesh->mvert; + data_cp.edge = mesh->medge; + + if (data_cp.cached == false) { + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); + data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree); + if (data_cp.cached == false) { + BLI_bitmap *loose_edges_mask = NULL; + int loose_edges_len = -1; + int edges_len = mesh->totedge; + + if (type == BVHTREE_FROM_LOOSEEDGES) { + loose_edges_mask = loose_edges_map_get( + data_cp.edge, edges_len, &loose_edges_len); + } + + data_cp.tree = bvhtree_from_mesh_edges_create_tree( + data_cp.vert, data_cp.edge, edges_len, + loose_edges_mask, loose_edges_len, 0.0, tree_type, 6); + + if (loose_edges_mask != NULL) { + MEM_freeN(loose_edges_mask); + } + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, type); + } + BLI_rw_mutex_unlock(&cache_rwlock); + } + break; + + case BVHTREE_FROM_FACES: + data_cp.nearest_callback = mesh_faces_nearest_point; + data_cp.raycast_callback = mesh_faces_spherecast; + + data_cp.vert = mesh->mvert; + data_cp.face = mesh->mface; + + if (data_cp.cached == false) { + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); + data_cp.cached = bvhcache_find( + mesh->runtime.bvh_cache, BVHTREE_FROM_FACES, &data_cp.tree); + if (data_cp.cached == false) { + int num_faces = mesh->totface; + BLI_assert(!(num_faces == 0 && mesh->totpoly != 0)); + + data_cp.tree = bvhtree_from_mesh_faces_create_tree( + 0.0, tree_type, 6, data_cp.vert, + data_cp.face, num_faces, NULL, -1); + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert( + &mesh->runtime.bvh_cache, data_cp.tree, BVHTREE_FROM_FACES); + } + BLI_rw_mutex_unlock(&cache_rwlock); + } + break; + + case BVHTREE_FROM_LOOPTRI: + data_cp.nearest_callback = mesh_looptri_nearest_point; + data_cp.raycast_callback = mesh_looptri_spherecast; + + data_cp.vert = mesh->mvert; + data_cp.loop = mesh->mloop; + + /* TODO: store looptris somewhere? */ + data_cp.looptri = BKE_mesh_runtime_looptri_ensure(mesh); + + if (data_cp.cached == false) { + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); + data_cp.cached = bvhcache_find( + mesh->runtime.bvh_cache, BVHTREE_FROM_LOOPTRI, &data_cp.tree); + if (data_cp.cached == false) { + int looptri_num = BKE_mesh_runtime_looptri_len(mesh); + /* this assert checks we have looptris, + * if not caller should use DM_ensure_looptri() */ + BLI_assert(!(looptri_num == 0 && mesh->totpoly != 0)); + + data_cp.tree = bvhtree_from_mesh_looptri_create_tree( + 0.0, tree_type, 6, + data_cp.vert, data_cp.loop, + data_cp.looptri, looptri_num, NULL, -1); + + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert( + &mesh->runtime.bvh_cache, data_cp.tree, BVHTREE_FROM_LOOPTRI); + } + BLI_rw_mutex_unlock(&cache_rwlock); + } + break; + } + + if (data_cp.tree != NULL) { +#ifdef DEBUG + if (BLI_bvhtree_get_tree_type(data_cp.tree) != tree_type) { + printf("tree_type %d obtained instead of %d\n", + BLI_bvhtree_get_tree_type(data_cp.tree), tree_type); + } +#endif + data_cp.cached = true; + memcpy(data, &data_cp, sizeof(*data)); + } + else { + free_bvhtree_from_mesh(&data_cp); + memset(data, 0, sizeof(*data)); + } + + return data_cp.tree; +} + /** \} */ @@ -1216,16 +1482,17 @@ typedef struct BVHCacheItem { /** * Queries a bvhcache for the cache bvhtree of the request type */ -BVHTree *bvhcache_find(BVHCache *cache, int type) +bool bvhcache_find(const BVHCache *cache, int type, BVHTree **r_tree) { while (cache) { const BVHCacheItem *item = cache->link; if (item->type == type) { - return item->tree; + *r_tree = item->tree; + return true; } cache = cache->next; } - return NULL; + return false; } bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree) @@ -1251,11 +1518,9 @@ void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type) { BVHCacheItem *item = NULL; - assert(tree != NULL); - assert(bvhcache_find(*cache_p, type) == NULL); + assert(bvhcache_find(*cache_p, type, &(BVHTree *){0}) == false); item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem"); - assert(item != NULL); item->type = type; item->tree = tree; @@ -1264,13 +1529,8 @@ void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type) } /** - * inits and frees a bvhcache + * frees a bvhcache */ -void bvhcache_init(BVHCache **cache_p) -{ - *cache_p = NULL; -} - static void bvhcacheitem_free(void *_item) { BVHCacheItem *item = (BVHCacheItem *)_item; |