diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2015-01-09 14:25:18 +0300 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2015-01-09 15:03:55 +0300 |
commit | 62cc4bab083893a85e451ab96455c9be60c04cc1 (patch) | |
tree | dd222d25c9d4ecbbe8c1ccd9f5317a1fdd0df7fd /source | |
parent | 17941860530693dfce76a4bf3d25e0e29610a20b (diff) |
BKE bvhutils: cleanup and refactor to make it more flexible.
You can now use lower-level '_ex' versions of bvh creators to only use part of
the mesh's elements in the BVH, and/or create bvh from non-DM sources.
Needed for transfer data.
Note edges extend version of bvh creator is not added here, not needed so far.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/BKE_bvhutils.h | 46 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/bvhutils.c | 574 |
2 files changed, 398 insertions, 222 deletions
diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h index 4bc8fc44bb4..a360511dcd3 100644 --- a/source/blender/blenkernel/BKE_bvhutils.h +++ b/source/blender/blenkernel/BKE_bvhutils.h @@ -31,6 +31,7 @@ * \ingroup bke */ +#include "BLI_bitmap.h" #include "BLI_kdopbvh.h" /* @@ -56,8 +57,8 @@ typedef struct BVHTreeFromMesh { struct MEdge *edge; /* only used for BVHTreeFromMeshEdges */ struct MFace *face; bool vert_allocated; - bool face_allocated; bool edge_allocated; + bool face_allocated; /* radius for raycast */ float sphere_radius; @@ -69,36 +70,28 @@ typedef struct BVHTreeFromMesh { } BVHTreeFromMesh; /* - * Builds a bvh tree where nodes are the vertexs of the given mesh. + * Builds a bvh tree where nodes are the relevant elements of the given mesh. * Configures BVHTreeFromMesh. * * The tree is build in mesh space coordinates, this means special care must be made on queries * so that the coordinates and rays are first translated on the mesh local coordinates. - * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse - * a BVHTree. + * Reason for this is that bvh_from_mesh_* can use a cache in some cases and so it becomes possible to reuse a BVHTree. * * free_bvhtree_from_mesh should be called when the tree is no longer needed. */ BVHTree *bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis); - -/* - * Builds a bvh tree where nodes are the faces of the given mesh. - * Configures BVHTreeFromMesh. - * - * The tree is build in mesh space coordinates, this means special care must be made on queries - * so that the coordinates and rays are first translated on the mesh local coordinates. - * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse - * a BVHTree. - * - * The returned value is the same as in data->tree, its only returned to make it easier to test - * the success - * - * free_bvhtree_from_mesh should be called when the tree is no longer needed. - */ -BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis); +BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data, struct MVert *vert, const int numVerts, + const bool vert_allocated, BLI_bitmap *mask, int numVerts_active, + float epsilon, int tree_type, int axis); BVHTree *bvhtree_from_mesh_edges(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis); +BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis); +BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data, struct MVert *vert, const bool vert_allocated, + struct MFace *face, const int numFaces, const bool face_allocated, + BLI_bitmap *mask, int numFaces_active, + float epsilon, int tree_type, int axis); + /* * Frees data allocated by a call to bvhtree_from_mesh_*. */ @@ -114,12 +107,13 @@ float nearest_point_in_tri_surface_squared(const float v0[3], const float v1[3], * BVHCache */ -//Using local coordinates -#define BVHTREE_FROM_FACES 0 -#define BVHTREE_FROM_VERTICES 1 -#define BVHTREE_FROM_EDGES 2 - -#define BVHTREE_FROM_FACES_EDITMESH 3 +/* Using local coordinates */ +enum { + BVHTREE_FROM_VERTS = 0, + BVHTREE_FROM_EDGES = 1, + BVHTREE_FROM_FACES = 2, + BVHTREE_FROM_FACES_EDITMESH = 3, +}; typedef struct LinkNode *BVHCache; diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c index a3b65b92051..1a4a4bd6bce 100644 --- a/source/blender/blenkernel/intern/bvhutils.c +++ b/source/blender/blenkernel/intern/bvhutils.c @@ -79,7 +79,7 @@ static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, con * BVH from meshes callbacks */ -/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces. +/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_faces. * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */ static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) { @@ -143,7 +143,7 @@ static void editmesh_faces_nearest_point(void *userdata, int index, const float } } -/* Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces. +/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_faces. * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */ static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) { @@ -212,7 +212,7 @@ static void editmesh_faces_spherecast(void *userdata, int index, const BVHTreeRa } } -/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges. +/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_edges. * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) { @@ -237,68 +237,140 @@ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3 } } -/* - * BVH builders - */ -/* Builds a bvh tree.. where nodes are the vertexs of the given mesh */ -BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis) +/* Helper, does all the point-spherecast work actually. */ +static void mesh_verts_spherecast_do( + const BVHTreeFromMesh *UNUSED(data), int index, const float v[3], const BVHTreeRay *ray, BVHTreeRayHit *hit) { - BVHTree *tree; - MVert *vert; - bool vert_allocated; + float dist; + const float *r1; + float r2[3], i1[3]; + r1 = ray->origin; + add_v3_v3v3(r2, r1, ray->direction); + + closest_to_line_segment_v3(i1, v, r1, r2); + + /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */ + if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) { + hit->index = index; + hit->dist = dist; + copy_v3_v3(hit->co, i1); + } +} - BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES); - BLI_rw_mutex_unlock(&cache_rwlock); +/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_verts. + * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */ +static void mesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata; + float *v = data->vert[index].co; - vert = DM_get_vert_array(dm, &vert_allocated); + mesh_verts_spherecast_do(data, index, v, ray, hit); +} - /* Not in cache */ - if (tree == NULL) { - BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES); - if (tree == NULL) { - int i; - int numVerts = dm->getNumVerts(dm); +/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_edges. + * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */ +static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata; + MVert *vert = data->vert; + MEdge *edge = &data->edge[index]; - if (vert != NULL) { - tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis); + const float radius_sq = SQUARE(data->sphere_radius); + float dist; + const float *v1, *v2, *r1; + float r2[3], i1[3], i2[3]; + v1 = vert[edge->v1].co; + v2 = vert[edge->v2].co; + + /* In case we get a zero-length edge, handle it as a point! */ + if (equals_v3v3(v1, v2)) { + mesh_verts_spherecast_do(data, index, v1, ray, hit); + return; + } - if (tree != NULL) { - for (i = 0; i < numVerts; i++) { - BLI_bvhtree_insert(tree, i, vert[i].co, 1); - } + r1 = ray->origin; + add_v3_v3v3(r2, r1, ray->direction); - BLI_bvhtree_balance(tree); + if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) { + /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */ + if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) { + const float e_fac = line_point_factor_v3(i1, v1, v2); + if (e_fac < 0.0f) { + copy_v3_v3(i1, v1); + } + else if (e_fac > 1.0f) { + copy_v3_v3(i1, v2); + } + /* Ensure ray is really close enough from edge! */ + if (len_squared_v3v3(i1, i2) <= radius_sq) { + hit->index = index; + hit->dist = dist; + copy_v3_v3(hit->co, i2); + } + } + } +} - /* Save on cache for later use */ -// printf("BVHTree built and saved on cache\n"); - bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTICES); +/* + * BVH builders + */ + +/* ***** Vertex ***** */ + +static BVHTree *bvhtree_from_mesh_verts_create_tree(float epsilon, int tree_type, int axis, + MVert *vert, const int numVerts, + BLI_bitmap *mask, int numVerts_active) +{ + BVHTree *tree = NULL; + int i; + + if (vert) { + if (mask && numVerts_active < 0) { + numVerts_active = 0; + for (i = 0; i < numVerts; i++) { + if (BLI_BITMAP_TEST_BOOL(mask, i)) { + numVerts_active++; } } } - BLI_rw_mutex_unlock(&cache_rwlock); - } - else { -// printf("BVHTree is already build, using cached tree\n"); + else if (!mask) { + numVerts_active = numVerts; + } + + tree = BLI_bvhtree_new(numVerts_active, epsilon, tree_type, axis); + + if (tree) { + for (i = 0; i < numVerts; i++) { + if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) { + continue; + } + BLI_bvhtree_insert(tree, i, vert[i].co, 1); + } + + BLI_bvhtree_balance(tree); + } } + return tree; +} - /* Setup BVHTreeFromMesh */ +static void bvhtree_from_mesh_verts_setup_data(BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached, float epsilon, + MVert *vert, const bool vert_allocated) +{ memset(data, 0, sizeof(*data)); - data->tree = tree; - if (data->tree) { - data->cached = true; + if (tree) { + data->tree = tree; + data->cached = is_cached; /* a NULL nearest callback works fine * remember the min distance to point is the same as the min distance to BV of point */ data->nearest_callback = NULL; - data->raycast_callback = NULL; + data->raycast_callback = mesh_verts_spherecast; data->vert = vert; data->vert_allocated = vert_allocated; - data->face = DM_get_tessface_array(dm, &data->face_allocated); + //data->face = DM_get_tessface_array(dm, &data->face_allocated); /* XXX WHY???? */ data->sphere_radius = epsilon; } @@ -307,184 +379,66 @@ BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float e MEM_freeN(vert); } } - - return data->tree; } -/* Builds a bvh tree.. where nodes are the faces of the given dm. */ -BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis) +/* Builds a bvh tree where nodes are the vertices of the given dm */ +BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis) { - BMEditMesh *em = data->em_evil; - const int bvhcache_type = em ? BVHTREE_FROM_FACES_EDITMESH : BVHTREE_FROM_FACES; BVHTree *tree; MVert *vert; - MFace *face; - bool vert_allocated = false, face_allocated = false; + bool vert_allocated; BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); - tree = bvhcache_find(&dm->bvhCache, bvhcache_type); + tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS); BLI_rw_mutex_unlock(&cache_rwlock); - if (em == NULL) { - vert = DM_get_vert_array(dm, &vert_allocated); - face = DM_get_tessface_array(dm, &face_allocated); - } + vert = DM_get_vert_array(dm, &vert_allocated); /* Not in cache */ if (tree == NULL) { BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); - tree = bvhcache_find(&dm->bvhCache, bvhcache_type); + tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS); if (tree == NULL) { - int i; - int numFaces; - - /* BMESH specific check that we have tessfaces, - * we _could_ tessellate here but rather not - campbell - * - * this assert checks we have tessfaces, - * if not caller should use DM_ensure_tessface() */ - if (em) { - numFaces = em->tottri; - } - else { - numFaces = dm->getNumTessFaces(dm); - BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0)); - } - - if (numFaces != 0) { - /* Create a bvh-tree of the given target */ - // printf("%s: building BVH, total=%d\n", __func__, numFaces); - tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis); - if (tree != NULL) { - if (em) { - const struct BMLoop *(*looptris)[3] = (void *)em->looptris; - - /* avoid double-up on face searches for quads-ngons */ - bool insert_prev = false; - BMFace *f_prev = NULL; - - /* data->em_evil is only set for snapping, and only for the mesh of the object - * which is currently open in edit mode. When set, the bvhtree should not contain - * faces that will interfere with snapping (e.g. faces that are hidden/selected - * or faces that have selected verts).*/ - - /* 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 < em->tottri; i++) { - const BMLoop **ltri = looptris[i]; - BMFace *f = ltri[0]->f; - bool insert; - - /* Start with the assumption the triangle should be included for snapping. */ - if (f == f_prev) { - insert = insert_prev; - } - else { - if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) { - /* Don't insert triangles tessellated from faces that are hidden - * or selected*/ - insert = false; - } - else { - BMLoop *l_iter, *l_first; - insert = true; - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) { - /* Don't insert triangles tessellated from faces that have - * any selected verts.*/ - insert = false; - break; - } - } while ((l_iter = l_iter->next) != l_first); - } - - /* skip if face doesn't change */ - f_prev = f; - insert_prev = insert; - } - - 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); - } - } - } - else { - if (vert != NULL && face != NULL) { - for (i = 0; i < numFaces; i++) { - float co[4][3]; - copy_v3_v3(co[0], vert[face[i].v1].co); - copy_v3_v3(co[1], vert[face[i].v2].co); - copy_v3_v3(co[2], vert[face[i].v3].co); - if (face[i].v4) - copy_v3_v3(co[3], vert[face[i].v4].co); - - BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3); - } - } - } - BLI_bvhtree_balance(tree); - - /* Save on cache for later use */ -// printf("BVHTree built and saved on cache\n"); - bvhcache_insert(&dm->bvhCache, tree, bvhcache_type); - } + tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, dm->getNumVerts(dm), 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_VERTS); } } BLI_rw_mutex_unlock(&cache_rwlock); } else { -// printf("BVHTree is already build, using cached tree\n"); + /* printf("BVHTree is already build, using cached tree\n"); */ } - /* Setup BVHTreeFromMesh */ - memset(data, 0, sizeof(*data)); - data->tree = tree; - data->em_evil = em; + bvhtree_from_mesh_verts_setup_data(data, tree, true, epsilon, vert, vert_allocated); - if (data->tree) { - data->cached = true; - - if (em) { - data->nearest_callback = editmesh_faces_nearest_point; - data->raycast_callback = editmesh_faces_spherecast; - } - else { - data->nearest_callback = mesh_faces_nearest_point; - data->raycast_callback = mesh_faces_spherecast; + return data->tree; +} - data->vert = vert; - data->vert_allocated = vert_allocated; - data->face = face; - data->face_allocated = face_allocated; - } +/** + * Builds a bvh tree where nodes are the given vertices (note: does not copy given mverts!). + * \param vert_allocated if true, vert freeing will be done when freeing data. + * \param mask if not null, true elements give which vert to add to BVH tree. + * \param numVerts_active if >= 0, number of active verts to add to BVH tree (else will be computed from mask). + */ +BVHTree *bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data, MVert *vert, const int numVerts, const bool vert_allocated, + BLI_bitmap *mask, int numVerts_active, + float epsilon, int tree_type, int axis) +{ + BVHTree *tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, numVerts, mask, numVerts_active); - data->sphere_radius = epsilon; - } - else { - if (vert_allocated) { - MEM_freeN(vert); - } - if (face_allocated) { - MEM_freeN(face); - } - } + /* Setup BVHTreeFromMesh */ + bvhtree_from_mesh_verts_setup_data(data, tree, false, epsilon, vert, vert_allocated); return data->tree; - } -/* Builds a bvh tree.. where nodes are the faces of the given dm. */ +/* ***** Edge ***** */ + +/* Builds a bvh tree where nodes are the edges of the given dm */ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis) { BVHTree *tree; @@ -521,7 +475,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e BLI_bvhtree_balance(tree); /* Save on cache for later use */ -// printf("BVHTree built and saved on cache\n"); + /* printf("BVHTree built and saved on cache\n"); */ bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_EDGES); } } @@ -529,7 +483,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e BLI_rw_mutex_unlock(&cache_rwlock); } else { -// printf("BVHTree is already build, using cached tree\n"); + /* printf("BVHTree is already build, using cached tree\n"); */ } @@ -541,7 +495,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e data->cached = true; data->nearest_callback = mesh_edges_nearest_point; - data->raycast_callback = NULL; + data->raycast_callback = mesh_edges_spherecast; data->vert = vert; data->vert_allocated = vert_allocated; @@ -559,15 +513,240 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e } } return data->tree; +} + +/* ***** Tessellated face ***** */ + +static BVHTree *bvhtree_from_mesh_faces_create_tree(float epsilon, int tree_type, int axis, + BMEditMesh *em, MVert *vert, MFace *face, const int numFaces, + BLI_bitmap *mask, int numFaces_active) +{ + BVHTree *tree = NULL; + int i; + + if (numFaces) { + if (mask && numFaces_active < 0) { + numFaces_active = 0; + for (i = 0; i < numFaces; i++) { + if (BLI_BITMAP_TEST_BOOL(mask, i)) { + numFaces_active++; + } + } + } + else if (!mask) { + numFaces_active = numFaces; + } + + /* Create a bvh-tree of the given target */ + /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */ + tree = BLI_bvhtree_new(numFaces_active, epsilon, tree_type, axis); + if (tree) { + if (em) { + const struct BMLoop *(*looptris)[3] = (void *)em->looptris; + + /* avoid double-up on face searches for quads-ngons */ + bool insert_prev = false; + BMFace *f_prev = NULL; + + /* data->em_evil is only set for snapping, and only for the mesh of the object + * which is currently open in edit mode. When set, the bvhtree should not contain + * faces that will interfere with snapping (e.g. faces that are hidden/selected + * or faces that have selected verts). */ + + /* 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 < numFaces; i++) { + const BMLoop **ltri = looptris[i]; + BMFace *f = ltri[0]->f; + bool insert = mask ? BLI_BITMAP_TEST_BOOL(mask, i) : true; + + /* Start with the assumption the triangle should be included for snapping. */ + if (f == f_prev) { + insert = insert_prev; + } + else if (insert) { + if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) { + /* Don't insert triangles tessellated from faces that are hidden or selected */ + insert = false; + } + else { + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) { + /* Don't insert triangles tessellated from faces that have any selected verts */ + insert = false; + break; + } + } while ((l_iter = l_iter->next) != l_first); + } + + /* skip if face doesn't change */ + f_prev = f; + insert_prev = insert; + } + + 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); + } + } + } + else { + if (vert && face) { + for (i = 0; i < numFaces; i++) { + float co[4][3]; + if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) { + continue; + } + copy_v3_v3(co[0], vert[face[i].v1].co); + copy_v3_v3(co[1], vert[face[i].v2].co); + copy_v3_v3(co[2], vert[face[i].v3].co); + if (face[i].v4) + copy_v3_v3(co[3], vert[face[i].v4].co); + + BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3); + } + } + } + BLI_bvhtree_balance(tree); + } + } + + return tree; +} + +static void bvhtree_from_mesh_faces_setup_data(BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached, + float epsilon, BMEditMesh *em, + MVert *vert, const bool vert_allocated, + MFace *face, const bool face_allocated) +{ + memset(data, 0, sizeof(*data)); + data->em_evil = em; + + if (tree) { + data->tree = tree; + data->cached = is_cached; + + if (em) { + data->nearest_callback = editmesh_faces_nearest_point; + data->raycast_callback = editmesh_faces_spherecast; + } + else { + data->nearest_callback = mesh_faces_nearest_point; + data->raycast_callback = mesh_faces_spherecast; + + data->vert = vert; + data->vert_allocated = vert_allocated; + data->face = face; + data->face_allocated = face_allocated; + } + + data->sphere_radius = epsilon; + } + else { + if (vert_allocated) { + MEM_freeN(vert); + } + if (face_allocated) { + MEM_freeN(face); + } + } +} + +/* Builds a bvh tree where nodes are the tesselated faces of the given dm */ +BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis) +{ + BMEditMesh *em = data->em_evil; + const int bvhcache_type = em ? BVHTREE_FROM_FACES_EDITMESH : BVHTREE_FROM_FACES; + BVHTree *tree; + MVert *vert = NULL; + MFace *face = NULL; + bool vert_allocated = false, face_allocated = false; + + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ); + tree = bvhcache_find(&dm->bvhCache, bvhcache_type); + BLI_rw_mutex_unlock(&cache_rwlock); + + if (em == NULL) { + vert = DM_get_vert_array(dm, &vert_allocated); + face = DM_get_tessface_array(dm, &face_allocated); + } + + /* Not in cache */ + if (tree == NULL) { + BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE); + tree = bvhcache_find(&dm->bvhCache, bvhcache_type); + if (tree == NULL) { + int numFaces; + + /* BMESH specific check that we have tessfaces, + * we _could_ tessellate here but rather not - campbell + * + * this assert checks we have tessfaces, + * if not caller should use DM_ensure_tessface() */ + if (em) { + numFaces = em->tottri; + } + else { + numFaces = dm->getNumTessFaces(dm); + BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0)); + } + + tree = bvhtree_from_mesh_faces_create_tree(epsilon, tree_type, axis, em, vert, face, numFaces, NULL, -1); + if (tree) { + /* Save on cache for later use */ + /* printf("BVHTree built and saved on cache\n"); */ + bvhcache_insert(&dm->bvhCache, tree, bvhcache_type); + } + } + BLI_rw_mutex_unlock(&cache_rwlock); + } + else { + /* printf("BVHTree is already build, using cached tree\n"); */ + } + + /* Setup BVHTreeFromMesh */ + bvhtree_from_mesh_faces_setup_data(data, tree, true, epsilon, em, vert, vert_allocated, face, face_allocated); + + return data->tree; +} + +/** + * Builds a bvh tree where nodes are the given tessellated faces (note: does not copy given mfaces!). + * \param vert_allocated if true, vert freeing will be done when freeing data. + * \param face_allocated if true, face freeing will be done when freeing data. + * \param mask if not null, true elements give which faces to add to BVH tree. + * \param numFaces_active if >= 0, number of active faces to add to BVH tree (else will be computed from mask). + */ +BVHTree *bvhtree_from_mesh_faces_ex(BVHTreeFromMesh *data, MVert *vert, const bool vert_allocated, + MFace *face, const int numFaces, const bool face_allocated, + BLI_bitmap *mask, int numFaces_active, float epsilon, int tree_type, int axis) +{ + BVHTree *tree = bvhtree_from_mesh_faces_create_tree(epsilon, tree_type, axis, NULL, vert, face, numFaces, + mask, numFaces_active); + + /* Setup BVHTreeFromMesh */ + bvhtree_from_mesh_faces_setup_data(data, tree, false, epsilon, NULL, vert, vert_allocated, face, face_allocated); + + return data->tree; } /* Frees data allocated by a call to bvhtree_from_mesh_*. */ void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data) { if (data->tree) { - if (!data->cached) + if (!data->cached) { BLI_bvhtree_free(data->tree); + } if (data->vert_allocated) { MEM_freeN(data->vert); @@ -584,7 +763,10 @@ void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data) } -/* BVHCache */ +/* + * BVHCache + */ + typedef struct BVHCacheItem { int type; BVHTree *tree; |