blender
/
blender
134
399
Fork 581
Code Issues 6.3k Pull Requests 754 Projects 19 Wiki Activity

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.
This commit is contained in:
Bastien Montagne 2015-01-09 12:25:18 +01:00
parent 1794186053
commit 62cc4bab08
2 changed files with 421 additions and 245 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

46
source/blender/blenkernel/BKE_bvhutils.h
View File

@ -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;

620
source/blender/blenkernel/intern/bvhutils.c
View File

@ -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,10 +237,151 @@ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3
}
}
/* 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)
{
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);
}
}
/* 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;
mesh_verts_spherecast_do(data, index, v, ray, hit);
}
/* 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];
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;
}
r1 = ray->origin;
add_v3_v3v3(r2, r1, ray->direction);
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);
}
}
}
}
/*
* BVH builders
*/
/* Builds a bvh tree.. where nodes are the vertexs of the given mesh */
/* ***** 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++;
}
}
}
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;
}
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));
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 = mesh_verts_spherecast;
data->vert = vert;
data->vert_allocated = vert_allocated;
//data->face = DM_get_tessface_array(dm, &data->face_allocated); /* XXX WHY???? */
data->sphere_radius = epsilon;
}
else {
if (vert_allocated) {
MEM_freeN(vert);
}
}
}
/* 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)
{
BVHTree *tree;
@ -248,7 +389,7 @@ BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float e
bool vert_allocated;
BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS);
BLI_rw_mutex_unlock(&cache_rwlock);
vert = DM_get_vert_array(dm, &vert_allocated);
@ -256,235 +397,48 @@ BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float e
/* Not in cache */
if (tree == NULL) {
BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS);
if (tree == NULL) {
int i;
int numVerts = dm->getNumVerts(dm);
if (vert != NULL) {
tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
if (tree != NULL) {
for (i = 0; i < numVerts; i++) {
BLI_bvhtree_insert(tree, i, vert[i].co, 1);
}
BLI_bvhtree_balance(tree);
/* Save on cache for later use */
// printf("BVHTree built and saved on cache\n");
bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTICES);
}
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;
if (data->tree) {
data->cached = true;
/* 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->vert = vert;
data->vert_allocated = vert_allocated;
data->face = DM_get_tessface_array(dm, &data->face_allocated);
data->sphere_radius = epsilon;
}
else {
if (vert_allocated) {
MEM_freeN(vert);
}
}
bvhtree_from_mesh_verts_setup_data(data, tree, true, epsilon, vert, vert_allocated);
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 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)
{
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;
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 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);
}
}
}
BLI_rw_mutex_unlock(&cache_rwlock);
}
else {
// printf("BVHTree is already build, using cached tree\n");
}
BVHTree *tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, numVerts, mask, numVerts_active);
/* Setup BVHTreeFromMesh */
memset(data, 0, sizeof(*data));
data->tree = tree;
data->em_evil = em;
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;
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);
}
}
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;