Differential D14479 Diff 49877 source/blender/blenkernel/intern/bvhutils.cc

Changeset View

Standalone View

source/blender/blenkernel/intern/bvhutils.cc

Show All 21 Lines
#include "BKE_bvhutils.h"		#include "BKE_bvhutils.h"
#include "BKE_editmesh.h"		#include "BKE_editmesh.h"
#include "BKE_mesh.h"		#include "BKE_mesh.h"
#include "BKE_mesh_runtime.h"		#include "BKE_mesh_runtime.h"

#include "MEM_guardedalloc.h"		#include "MEM_guardedalloc.h"

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name BVHCache		/** \name BVHCache
		brechtUnsubmitted Done Inline Actions Don't use global variables, seems like this could just be a function parameter? brecht: Don't use global variables, seems like this could just be a function parameter?
		mano-wiiAuthorUnsubmitted Done Inline Actions The intent of the patch is to make the API more readable, and since the `isolate` parameter has a restricted and somewhat complicated usage, I thought it best to make it an internal local variable. But I edited the code and made it a parameter. mano-wii: The intent of the patch is to make the API more readable, and since the `isolate` parameter has…
* \{ */		* \{ */

struct BVHCacheItem {		struct BVHCacheItem {
bool is_filled;		bool is_filled;
BVHTree *tree;		BVHTree *tree;
};		};

struct BVHCache {		struct BVHCache {
▲ Show 20 Lines • Show All 521 Lines • ▼ Show 20 Lines
/*		/*
* BVH builders		* BVH builders
*/		*/

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name Vertex Builder		/** \name Vertex Builder
* \{ */		* \{ */

		static void bvhtree_from_mesh_setup_data(BVHTree *tree,
		const BVHCacheType bvh_cache_type,
		const MVert *vert,
		const MEdge *edge,
		const MFace *face,
		const MLoop *loop,
		const MLoopTri *looptri,
		const float (*vert_normals)[3],
		BVHTreeFromMesh *r_data)
		{
		memset(r_data, 0, sizeof(*r_data));

		r_data->tree = tree;

		r_data->vert = vert;
		r_data->edge = edge;
		r_data->face = face;
		r_data->loop = loop;
		r_data->looptri = looptri;
		r_data->vert_normals = vert_normals;

		switch (bvh_cache_type) {
		case BVHTREE_FROM_VERTS:
		case BVHTREE_FROM_LOOSEVERTS:
		/* a nullptr nearest callback works fine
		* remember the min distance to point is the same as the min distance to BV of point */
		r_data->nearest_callback = nullptr;
		r_data->raycast_callback = mesh_verts_spherecast;
		break;

		case BVHTREE_FROM_EDGES:
		case BVHTREE_FROM_LOOSEEDGES:
		r_data->nearest_callback = mesh_edges_nearest_point;
		r_data->raycast_callback = mesh_edges_spherecast;
		break;
		case BVHTREE_FROM_FACES:
		r_data->nearest_callback = mesh_faces_nearest_point;
		r_data->raycast_callback = mesh_faces_spherecast;
		break;
		case BVHTREE_FROM_LOOPTRI:
		case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:
		r_data->nearest_callback = mesh_looptri_nearest_point;
		r_data->raycast_callback = mesh_looptri_spherecast;
		break;
		case BVHTREE_FROM_EM_VERTS:
		case BVHTREE_FROM_EM_EDGES:
		case BVHTREE_FROM_EM_LOOPTRI:
		case BVHTREE_MAX_ITEM:
		BLI_assert(false);
		break;
		}
		}

static BVHTree *bvhtree_from_editmesh_verts_create_tree(float epsilon,		static BVHTree *bvhtree_from_editmesh_verts_create_tree(float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
BMEditMesh *em,		BMEditMesh *em,
const BLI_bitmap *verts_mask,		const BLI_bitmap *verts_mask,
int verts_num_active)		int verts_num_active)
{		{
BM_mesh_elem_table_ensure(em->bm, BM_VERT);		BM_mesh_elem_table_ensure(em->bm, BM_VERT);
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines	if (tree) {
}		}
BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);		BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
}		}
}		}

return tree;		return tree;
}		}

static void bvhtree_from_mesh_verts_setup_data(BVHTreeFromMesh *data,
BVHTree *tree,
const bool is_cached,
const MVert *vert,
const bool vert_allocated)
{
memset(data, 0, sizeof(*data));

data->tree = tree;
data->cached = is_cached;

/* a nullptr nearest callback works fine
* remember the min distance to point is the same as the min distance to BV of point */
data->nearest_callback = nullptr;
data->raycast_callback = mesh_verts_spherecast;

data->vert = vert;
data->vert_allocated = vert_allocated;
}

BVHTree bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh data,		BVHTree bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh data,
BMEditMesh *em,		BMEditMesh *em,
const BLI_bitmap *verts_mask,		const BLI_bitmap *verts_mask,
int verts_num_active,		int verts_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
BVHTree *tree = nullptr;		BVHTree *tree = nullptr;

if (bvh_cache_p) {
bool lock_started = false;
data->cached = bvhcache_find(
bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);

if (data->cached == false) {
tree = bvhtree_from_editmesh_verts_create_tree(		tree = bvhtree_from_editmesh_verts_create_tree(
epsilon, tree_type, axis, em, verts_mask, verts_num_active);		epsilon, tree_type, axis, em, verts_mask, verts_num_active);
bvhtree_balance(tree, true);		bvhtree_balance(tree, isolate);

/* Save on cache for later use */		if (data && tree) {
// printf("BVHTree built and saved on cache\n");
bvhcache_insert(*bvh_cache_p, tree, bvh_cache_type);
data->cached = true;
}
bvhcache_unlock(*bvh_cache_p, lock_started);
}
else {
tree = bvhtree_from_editmesh_verts_create_tree(
epsilon, tree_type, axis, em, verts_mask, verts_num_active);
bvhtree_balance(tree, false);
}

if (tree) {
memset(data, 0, sizeof(*data));		memset(data, 0, sizeof(*data));
data->tree = tree;		data->tree = tree;
data->em = em;		data->em = em;
data->nearest_callback = nullptr;		data->nearest_callback = nullptr;
data->raycast_callback = editmesh_verts_spherecast;		data->raycast_callback = editmesh_verts_spherecast;
data->cached = bvh_cache_p != nullptr;
}		}

return tree;		return tree;
}		}

BVHTree *bvhtree_from_editmesh_verts(		BVHTree *bvhtree_from_editmesh_verts(
BVHTreeFromEditMesh data, BMEditMesh em, float epsilon, int tree_type, int axis)		BVHTreeFromEditMesh data, BMEditMesh em, float epsilon, int tree_type, int axis)
{		{
return bvhtree_from_editmesh_verts_ex(		return bvhtree_from_editmesh_verts_ex(data, em, nullptr, -1, epsilon, tree_type, axis, false);
data, em, nullptr, -1, epsilon, tree_type, axis, BVHTREE_FROM_VERTS, nullptr, nullptr);
}		}

BVHTree bvhtree_from_mesh_verts_ex(BVHTreeFromMesh data,		BVHTree bvhtree_from_mesh_verts_ex(BVHTreeFromMesh data,
const MVert *vert,		const MVert *vert,
const int verts_num,		const int verts_num,
const bool vert_allocated,		const bool vert_allocated,
const BLI_bitmap *verts_mask,		const BLI_bitmap *verts_mask,
int verts_num_active,		int verts_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
bool in_cache = false;
bool lock_started = false;
BVHTree *tree = nullptr;		BVHTree *tree = nullptr;
if (bvh_cache_p) {
in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
}

if (in_cache == false) {
tree = bvhtree_from_mesh_verts_create_tree(		tree = bvhtree_from_mesh_verts_create_tree(
epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);		epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);
bvhtree_balance(tree, bvh_cache_p != nullptr);		bvhtree_balance(tree, isolate);

if (bvh_cache_p) {
/* Save on cache for later use */
// printf("BVHTree built and saved on cache\n");
BVHCache bvh_cache = bvh_cache_p;
bvhcache_insert(bvh_cache, tree, bvh_cache_type);
in_cache = true;
}
}

if (bvh_cache_p) {
bvhcache_unlock(*bvh_cache_p, lock_started);
}

		if (data) {
/* Setup BVHTreeFromMesh */		/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_verts_setup_data(data, tree, in_cache, vert, vert_allocated);		bvhtree_from_mesh_setup_data(
		tree, BVHTREE_FROM_VERTS, vert, nullptr, nullptr, nullptr, nullptr, nullptr, data);
		data->vert_allocated = vert_allocated;
		}

return tree;		return tree;
}		}

/** \} */		/** \} */

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name Edge Builder		/** \name Edge Builder
▲ Show 20 Lines • Show All 71 Lines • ▼ Show 20 Lines	if (tree) {
BLI_bvhtree_insert(tree, i, co[0], 2);		BLI_bvhtree_insert(tree, i, co[0], 2);
}		}
}		}
}		}

return tree;		return tree;
}		}

static void bvhtree_from_mesh_edges_setup_data(BVHTreeFromMesh *data,
BVHTree *tree,
const bool is_cached,
const MVert *vert,
const bool vert_allocated,
const MEdge *edge,
const bool edge_allocated)
{
memset(data, 0, sizeof(*data));

data->tree = tree;

data->cached = is_cached;

data->nearest_callback = mesh_edges_nearest_point;
data->raycast_callback = mesh_edges_spherecast;

data->vert = vert;
data->vert_allocated = vert_allocated;
data->edge = edge;
data->edge_allocated = edge_allocated;
}

BVHTree bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh data,		BVHTree bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh data,
BMEditMesh *em,		BMEditMesh *em,
const BLI_bitmap *edges_mask,		const BLI_bitmap *edges_mask,
int edges_num_active,		int edges_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
BVHTree *tree = nullptr;		BVHTree *tree;

if (bvh_cache_p) {
bool lock_started = false;
data->cached = bvhcache_find(
bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
BVHCache bvh_cache = bvh_cache_p;
if (data->cached == false) {
tree = bvhtree_from_editmesh_edges_create_tree(		tree = bvhtree_from_editmesh_edges_create_tree(
epsilon, tree_type, axis, em, edges_mask, edges_num_active);		epsilon, tree_type, axis, em, edges_mask, edges_num_active);
bvhtree_balance(tree, true);		bvhtree_balance(tree, isolate);
/* Save on cache for later use */
// printf("BVHTree built and saved on cache\n");
bvhcache_insert(bvh_cache, tree, bvh_cache_type);
data->cached = true;
}
bvhcache_unlock(bvh_cache, lock_started);
}
else {
tree = bvhtree_from_editmesh_edges_create_tree(
epsilon, tree_type, axis, em, edges_mask, edges_num_active);
bvhtree_balance(tree, false);
}

if (tree) {		if (data && tree) {
memset(data, 0, sizeof(*data));		memset(data, 0, sizeof(*data));
data->tree = tree;		data->tree = tree;
data->em = em;		data->em = em;
data->nearest_callback = nullptr; /* TODO */		data->nearest_callback = nullptr; /* TODO */
data->raycast_callback = nullptr; /* TODO */		data->raycast_callback = nullptr; /* TODO */
data->cached = bvh_cache_p != nullptr;
}		}

return tree;		return tree;
}		}

BVHTree *bvhtree_from_editmesh_edges(		BVHTree *bvhtree_from_editmesh_edges(
BVHTreeFromEditMesh data, BMEditMesh em, float epsilon, int tree_type, int axis)		BVHTreeFromEditMesh data, BMEditMesh em, float epsilon, int tree_type, int axis)
{		{
return bvhtree_from_editmesh_edges_ex(		return bvhtree_from_editmesh_edges_ex(data, em, nullptr, -1, epsilon, tree_type, axis, false);
data, em, nullptr, -1, epsilon, tree_type, axis, BVHTREE_FROM_VERTS, nullptr, nullptr);
}		}

BVHTree bvhtree_from_mesh_edges_ex(BVHTreeFromMesh data,		BVHTree bvhtree_from_mesh_edges_ex(BVHTreeFromMesh data,
const MVert *vert,		const MVert *vert,
const bool vert_allocated,		const bool vert_allocated,
const MEdge *edge,		const MEdge *edge,
const int edges_num,		const int edges_num,
const bool edge_allocated,		const bool edge_allocated,
const BLI_bitmap *edges_mask,		const BLI_bitmap *edges_mask,
int edges_num_active,		int edges_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
bool in_cache = false;
bool lock_started = false;
BVHTree *tree = nullptr;		BVHTree *tree = nullptr;
if (bvh_cache_p) {
in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
}

if (in_cache == false) {
tree = bvhtree_from_mesh_edges_create_tree(		tree = bvhtree_from_mesh_edges_create_tree(
vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);		vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);

if (bvh_cache_p) {		bvhtree_balance(tree, isolate);
bvhtree_balance(tree, true);

BVHCache bvh_cache = bvh_cache_p;
/* Save on cache for later use */
// printf("BVHTree built and saved on cache\n");
bvhcache_insert(bvh_cache, tree, bvh_cache_type);
in_cache = true;
}
else {
bvhtree_balance(tree, false);
}
}

if (bvh_cache_p) {
bvhcache_unlock(*bvh_cache_p, lock_started);
}

		if (data) {
/* Setup BVHTreeFromMesh */		/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_edges_setup_data(		bvhtree_from_mesh_setup_data(
data, tree, in_cache, vert, vert_allocated, edge, edge_allocated);		tree, BVHTREE_FROM_EDGES, vert, edge, nullptr, nullptr, nullptr, nullptr, data);
		data->vert_allocated = vert_allocated;
		data->vert_allocated = edge_allocated;
		}

return tree;		return tree;
}		}

/** \} */		/** \} */

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name Tessellated Face Builder		/** \name Tessellated Face Builder
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines	if (tree) {
}		}
BLI_assert(BLI_bvhtree_get_len(tree) == faces_num_active);		BLI_assert(BLI_bvhtree_get_len(tree) == faces_num_active);
}		}
}		}

return tree;		return tree;
}		}

static void bvhtree_from_mesh_faces_setup_data(BVHTreeFromMesh *data,
BVHTree *tree,
const bool is_cached,
const MVert *vert,
const bool vert_allocated,
const MFace *face,
const bool face_allocated)
{
memset(data, 0, sizeof(*data));

data->tree = tree;
data->cached = is_cached;

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

BVHTree bvhtree_from_mesh_faces_ex(BVHTreeFromMesh data,		BVHTree bvhtree_from_mesh_faces_ex(BVHTreeFromMesh data,
const MVert *vert,		const MVert *vert,
const bool vert_allocated,		const bool vert_allocated,
const MFace *face,		const MFace *face,
const int numFaces,		const int numFaces,
const bool face_allocated,		const bool face_allocated,
const BLI_bitmap *faces_mask,		const BLI_bitmap *faces_mask,
int faces_num_active,		int faces_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
bool in_cache = false;
bool lock_started = false;
BVHTree *tree = nullptr;		BVHTree *tree = nullptr;
if (bvh_cache_p) {
in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
}

if (in_cache == false) {
tree = bvhtree_from_mesh_faces_create_tree(		tree = bvhtree_from_mesh_faces_create_tree(
epsilon, tree_type, axis, vert, face, numFaces, faces_mask, faces_num_active);		epsilon, tree_type, axis, vert, face, numFaces, faces_mask, faces_num_active);
bvhtree_balance(tree, bvh_cache_p != nullptr);		bvhtree_balance(tree, isolate);

if (bvh_cache_p) {
/* Save on cache for later use */
// printf("BVHTree built and saved on cache\n");
BVHCache bvh_cache = bvh_cache_p;
bvhcache_insert(bvh_cache, tree, bvh_cache_type);
in_cache = true;
}
}

if (bvh_cache_p) {
bvhcache_unlock(*bvh_cache_p, lock_started);
}

		if (data) {
/* Setup BVHTreeFromMesh */		/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_faces_setup_data(		bvhtree_from_mesh_setup_data(
data, tree, in_cache, vert, vert_allocated, face, face_allocated);		tree, BVHTREE_FROM_FACES, vert, nullptr, face, nullptr, nullptr, nullptr, data);
		data->vert_allocated = vert_allocated;
		data->face_allocated = face_allocated;
		}

return tree;		return tree;
}		}

/** \} */		/** \} */

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name LoopTri Face Builder		/** \name LoopTri Face Builder
▲ Show 20 Lines • Show All 88 Lines • ▼ Show 20 Lines	if (tree) {
}		}
BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);		BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
}		}
}		}

return tree;		return tree;
}		}

static void bvhtree_from_mesh_looptri_setup_data(BVHTreeFromMesh *data,
BVHTree *tree,
const bool is_cached,
const MVert *vert,
const bool vert_allocated,
const MLoop *mloop,
const bool loop_allocated,
const MLoopTri *looptri,
const bool looptri_allocated)
{
memset(data, 0, sizeof(*data));

data->tree = tree;
data->cached = is_cached;

data->nearest_callback = mesh_looptri_nearest_point;
data->raycast_callback = mesh_looptri_spherecast;

data->vert = vert;
data->vert_allocated = vert_allocated;
data->loop = mloop;
data->loop_allocated = loop_allocated;
data->looptri = looptri;
data->looptri_allocated = looptri_allocated;
}

BVHTree bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh data,		BVHTree bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh data,
BMEditMesh *em,		BMEditMesh *em,
const BLI_bitmap *looptri_mask,		const BLI_bitmap *looptri_mask,
int looptri_num_active,		int looptri_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
/* BMESH specific check that we have tessfaces,		/* BMESH specific check that we have tessfaces,
* we _could_ tessellate here but rather not - campbell */		* we _could_ tessellate here but rather not - campbell */

BVHTree *tree = nullptr;		BVHTree *tree;
if (bvh_cache_p) {
bool lock_started = false;
bool in_cache = bvhcache_find(
bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
BVHCache bvh_cache = bvh_cache_p;
if (in_cache == false) {
tree = bvhtree_from_editmesh_looptri_create_tree(
epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
bvhtree_balance(tree, true);

/* Save on cache for later use */
// printf("BVHTree built and saved on cache\n");
bvhcache_insert(bvh_cache, tree, bvh_cache_type);
}
bvhcache_unlock(bvh_cache, lock_started);
}
else {
tree = bvhtree_from_editmesh_looptri_create_tree(		tree = bvhtree_from_editmesh_looptri_create_tree(
epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);		epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
bvhtree_balance(tree, false);		bvhtree_balance(tree, isolate);
}

if (tree) {		if (data && tree) {
data->tree = tree;		data->tree = tree;
data->nearest_callback = editmesh_looptri_nearest_point;		data->nearest_callback = editmesh_looptri_nearest_point;
data->raycast_callback = editmesh_looptri_spherecast;		data->raycast_callback = editmesh_looptri_spherecast;
data->em = em;		data->em = em;
data->cached = bvh_cache_p != nullptr;
}		}
return tree;		return tree;
}		}

BVHTree *bvhtree_from_editmesh_looptri(		BVHTree *bvhtree_from_editmesh_looptri(
BVHTreeFromEditMesh data, BMEditMesh em, float epsilon, int tree_type, int axis)		BVHTreeFromEditMesh data, BMEditMesh em, float epsilon, int tree_type, int axis)
{		{
return bvhtree_from_editmesh_looptri_ex(		return bvhtree_from_editmesh_looptri_ex(data, em, nullptr, -1, epsilon, tree_type, axis, false);
data, em, nullptr, -1, epsilon, tree_type, axis, BVHTREE_FROM_VERTS, nullptr, nullptr);
}		}

BVHTree bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh data,		BVHTree bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh data,
const struct MVert *vert,		const struct MVert *vert,
const bool vert_allocated,		const bool vert_allocated,
const struct MLoop *mloop,		const struct MLoop *mloop,
const bool loop_allocated,		const bool loop_allocated,
const struct MLoopTri *looptri,		const struct MLoopTri *looptri,
const int looptri_num,		const int looptri_num,
const bool looptri_allocated,		const bool looptri_allocated,
const BLI_bitmap *looptri_mask,		const BLI_bitmap *looptri_mask,
int looptri_num_active,		int looptri_num_active,
float epsilon,		float epsilon,
int tree_type,		int tree_type,
int axis,		int axis,
const BVHCacheType bvh_cache_type,		const bool isolate)
BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)
{		{
bool in_cache = false;
bool lock_started = false;
BVHTree *tree = nullptr;		BVHTree *tree = nullptr;
if (bvh_cache_p) {
in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
}

if (in_cache == false) {
/* Setup BVHTreeFromMesh */		/* Setup BVHTreeFromMesh */
tree = bvhtree_from_mesh_looptri_create_tree(epsilon,		tree = bvhtree_from_mesh_looptri_create_tree(epsilon,
tree_type,		tree_type,
axis,		axis,
vert,		vert,
mloop,		mloop,
looptri,		looptri,
looptri_num,		looptri_num,
looptri_mask,		looptri_mask,
looptri_num_active);		looptri_num_active);

bvhtree_balance(tree, bvh_cache_p != nullptr);		bvhtree_balance(tree, isolate);

if (bvh_cache_p) {
BVHCache bvh_cache = bvh_cache_p;
bvhcache_insert(bvh_cache, tree, bvh_cache_type);
in_cache = true;
}
}

if (bvh_cache_p) {
bvhcache_unlock(*bvh_cache_p, lock_started);
}

		if (data) {
/* Setup BVHTreeFromMesh */		/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_looptri_setup_data(data,		bvhtree_from_mesh_setup_data(
tree,		tree, BVHTREE_FROM_LOOPTRI, vert, nullptr, nullptr, mloop, looptri, nullptr, data);
in_cache,		data->vert_allocated = vert_allocated;
vert,		data->loop_allocated = loop_allocated;
vert_allocated,		data->looptri_allocated = looptri_allocated;
mloop,		}
loop_allocated,
looptri,
looptri_allocated);

return tree;		return tree;
}		}

static BLI_bitmap loose_verts_map_get(const MEdge medge,		static BLI_bitmap loose_verts_map_get(const MEdge medge,
int edges_num,		int edges_num,
const MVert *UNUSED(mvert),		const MVert *UNUSED(mvert),
int verts_num,		int verts_num,
▲ Show 20 Lines • Show All 72 Lines • ▼ Show 20 Lines	static BLI_bitmap looptri_no_hidden_map_get(const MPoly mpoly,
return looptri_mask;		return looptri_mask;
}		}

BVHTree BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh data,		BVHTree BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh data,
const struct Mesh *mesh,		const struct Mesh *mesh,
const BVHCacheType bvh_cache_type,		const BVHCacheType bvh_cache_type,
const int tree_type)		const int tree_type)
{		{
BVHTree *tree = nullptr;
BVHCache bvh_cache_p = (BVHCache )&mesh->runtime.bvh_cache;		BVHCache bvh_cache_p = (BVHCache )&mesh->runtime.bvh_cache;
ThreadMutex mesh_eval_mutex = (ThreadMutex )mesh->runtime.eval_mutex;		ThreadMutex mesh_eval_mutex = (ThreadMutex )mesh->runtime.eval_mutex;

const bool is_cached = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, nullptr, nullptr);		/* Setup BVHTreeFromMesh */
		bvhtree_from_mesh_setup_data(
		nullptr,
		bvh_cache_type,
		mesh->mvert,
		mesh->medge,
		mesh->mface,
		mesh->mloop,
		ELEM(bvh_cache_type, BVHTREE_FROM_LOOPTRI, BVHTREE_FROM_LOOPTRI_NO_HIDDEN) ?
		BKE_mesh_runtime_looptri_ensure(mesh) :
		nullptr,
		BKE_mesh_vertex_normals_ensure(mesh),
		data);

if (is_cached && tree == nullptr) {		bool lock_started = false;
memset(data, 0, sizeof(*data));		data->cached = bvhcache_find(
return tree;		bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);

		if (data->cached) {
		BLI_assert(lock_started == false);
		return data->tree;
		brechtUnsubmitted Done Inline Actions Is unlocking needed here? In the previous code I don't see it being conditional on `is_cached && tree == nullptr`. brecht: Is unlocking needed here? In the previous code I don't see it being conditional on `is_cached…
		mano-wiiAuthorUnsubmitted Done Inline Actions Not necessary. If the tree is already in cache, the lock has not started. mano-wii: Not necessary. If the tree is already in cache, the lock has not started.
}		}

		/* Create BVHTree. */

switch (bvh_cache_type) {		switch (bvh_cache_type) {
case BVHTREE_FROM_VERTS:		case BVHTREE_FROM_VERTS:
case BVHTREE_FROM_LOOSEVERTS:		case BVHTREE_FROM_LOOSEVERTS: {
if (is_cached == false) {
BLI_bitmap *loose_verts_mask = nullptr;		BLI_bitmap *loose_verts_mask = nullptr;
int loose_vert_len = -1;		int loose_vert_len = -1;
int verts_len = mesh->totvert;		int verts_len = mesh->totvert;

if (bvh_cache_type == BVHTREE_FROM_LOOSEVERTS) {		if (bvh_cache_type == BVHTREE_FROM_LOOSEVERTS) {
loose_verts_mask = loose_verts_map_get(		loose_verts_mask = loose_verts_map_get(
mesh->medge, mesh->totedge, mesh->mvert, verts_len, &loose_vert_len);		mesh->medge, mesh->totedge, mesh->mvert, verts_len, &loose_vert_len);
}		}

tree = bvhtree_from_mesh_verts_ex(data,		data->tree = bvhtree_from_mesh_verts_ex(nullptr,
mesh->mvert,		mesh->mvert,
verts_len,		verts_len,
false,		false,
loose_verts_mask,		loose_verts_mask,
loose_vert_len,		loose_vert_len,
0.0f,		0.0f,
tree_type,		tree_type,
6,		6,
bvh_cache_type,		lock_started);
bvh_cache_p,
mesh_eval_mutex);

if (loose_verts_mask != nullptr) {		if (loose_verts_mask != nullptr) {
MEM_freeN(loose_verts_mask);		MEM_freeN(loose_verts_mask);
}		}
}		} break;
else {
/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_verts_setup_data(data, tree, true, mesh->mvert, false);
}
break;

case BVHTREE_FROM_EDGES:		case BVHTREE_FROM_EDGES:
case BVHTREE_FROM_LOOSEEDGES:		case BVHTREE_FROM_LOOSEEDGES: {
if (is_cached == false) {
BLI_bitmap *loose_edges_mask = nullptr;		BLI_bitmap *loose_edges_mask = nullptr;
int loose_edges_len = -1;		int loose_edges_len = -1;
int edges_len = mesh->totedge;		int edges_len = mesh->totedge;

if (bvh_cache_type == BVHTREE_FROM_LOOSEEDGES) {		if (bvh_cache_type == BVHTREE_FROM_LOOSEEDGES) {
loose_edges_mask = loose_edges_map_get(mesh->medge, edges_len, &loose_edges_len);		loose_edges_mask = loose_edges_map_get(mesh->medge, edges_len, &loose_edges_len);
}		}

tree = bvhtree_from_mesh_edges_ex(data,		data->tree = bvhtree_from_mesh_edges_ex(nullptr,
mesh->mvert,		mesh->mvert,
false,		false,
mesh->medge,		mesh->medge,
edges_len,		edges_len,
false,		false,
loose_edges_mask,		loose_edges_mask,
loose_edges_len,		loose_edges_len,
0.0,		0.0,
tree_type,		tree_type,
6,		6,
bvh_cache_type,		lock_started);
bvh_cache_p,
mesh_eval_mutex);

if (loose_edges_mask != nullptr) {		if (loose_edges_mask != nullptr) {
MEM_freeN(loose_edges_mask);		MEM_freeN(loose_edges_mask);
}		}
}		} break;
else {
/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_edges_setup_data(
data, tree, true, mesh->mvert, false, mesh->medge, false);
}
break;

case BVHTREE_FROM_FACES:		case BVHTREE_FROM_FACES: {
if (is_cached == false) {
int num_faces = mesh->totface;		int num_faces = mesh->totface;
BLI_assert(!(num_faces == 0 && mesh->totpoly != 0));		BLI_assert(!(num_faces == 0 && mesh->totpoly != 0));

tree = bvhtree_from_mesh_faces_ex(data,		data->tree = bvhtree_from_mesh_faces_ex(nullptr,
mesh->mvert,		mesh->mvert,
false,		false,
mesh->mface,		mesh->mface,
num_faces,		num_faces,
false,		false,
nullptr,		nullptr,
-1,		-1,
0.0,		0.0,
tree_type,		tree_type,
6,		6,
bvh_cache_type,		lock_started);
bvh_cache_p,		} break;
mesh_eval_mutex);
}
else {
/* Setup BVHTreeFromMesh */
bvhtree_from_mesh_faces_setup_data(
data, tree, true, mesh->mvert, false, mesh->mface, false);
}
break;

case BVHTREE_FROM_LOOPTRI:		case BVHTREE_FROM_LOOPTRI:
case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:		case BVHTREE_FROM_LOOPTRI_NO_HIDDEN: {
if (is_cached == false) {
const MLoopTri *mlooptri = BKE_mesh_runtime_looptri_ensure(mesh);
int looptri_len = BKE_mesh_runtime_looptri_len(mesh);		int looptri_len = BKE_mesh_runtime_looptri_len(mesh);

int looptri_mask_active_len = -1;		int looptri_mask_active_len = -1;
BLI_bitmap *looptri_mask = nullptr;		BLI_bitmap *looptri_mask = nullptr;
if (bvh_cache_type == BVHTREE_FROM_LOOPTRI_NO_HIDDEN) {		if (bvh_cache_type == BVHTREE_FROM_LOOPTRI_NO_HIDDEN) {
looptri_mask = looptri_no_hidden_map_get(		looptri_mask = looptri_no_hidden_map_get(
mesh->mpoly, looptri_len, &looptri_mask_active_len);		mesh->mpoly, looptri_len, &looptri_mask_active_len);
}		}

tree = bvhtree_from_mesh_looptri_ex(data,		data->tree = bvhtree_from_mesh_looptri_ex(nullptr,
mesh->mvert,		mesh->mvert,
false,		false,
mesh->mloop,		mesh->mloop,
false,		false,
mlooptri,		data->looptri,
looptri_len,		looptri_len,
false,		false,
looptri_mask,		looptri_mask,
looptri_mask_active_len,		looptri_mask_active_len,
0.0,		0.0,
tree_type,		tree_type,
6,		6,
bvh_cache_type,		lock_started);
bvh_cache_p,
mesh_eval_mutex);

if (looptri_mask != nullptr) {		if (looptri_mask != nullptr) {
MEM_freeN(looptri_mask);		MEM_freeN(looptri_mask);
}		}
}		} break;
else {
/* Setup BVHTreeFromMesh */
const MLoopTri *mlooptri = BKE_mesh_runtime_looptri_ensure(mesh);
bvhtree_from_mesh_looptri_setup_data(
data, tree, true, mesh->mvert, false, mesh->mloop, false, mlooptri, false);
}
break;
case BVHTREE_FROM_EM_VERTS:		case BVHTREE_FROM_EM_VERTS:
case BVHTREE_FROM_EM_EDGES:		case BVHTREE_FROM_EM_EDGES:
case BVHTREE_FROM_EM_LOOPTRI:		case BVHTREE_FROM_EM_LOOPTRI:
case BVHTREE_MAX_ITEM:		case BVHTREE_MAX_ITEM:
BLI_assert(false);		BLI_assert(false);
break;		break;
}		}

if (data->tree != nullptr) {		if (bvh_cache_p) {
		/* Save on cache for later use */
		// printf("BVHTree built and saved on cache\n");
		BLI_assert(data->cached == false);
		data->cached = true;
		brechtUnsubmitted Done Inline Actions Is this re-inserting already cached BVHs? brecht: Is this re-inserting already cached BVHs?
		mano-wiiAuthorUnsubmitted Done Inline Actions Oh yeah! Terrible mistake! Fixed! mano-wii: Oh yeah! Terrible mistake! Fixed!
		bvhcache_insert(*bvh_cache_p, data->tree, bvh_cache_type);
		bvhcache_unlock(*bvh_cache_p, lock_started);
		brechtUnsubmitted Done Inline Actions This should be set before unlocking. brecht: This should be set before unlocking.
		mano-wiiAuthorUnsubmitted Done Inline Actions `data->cache`? I'm not sure if it is affected by the lock. Moved. mano-wii: `data->cache`? I'm not sure if it is affected by the lock. Moved.
		}

#ifdef DEBUG		#ifdef DEBUG
		if (data->tree) {
if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {		if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {
printf("tree_type %d obtained instead of %d\n",		printf("tree_type %d obtained instead of %d\n",
BLI_bvhtree_get_tree_type(data->tree),		BLI_bvhtree_get_tree_type(data->tree),
tree_type);		tree_type);
}		}
#endif
BLI_assert(data->cached);
}		}
else {		#endif
free_bvhtree_from_mesh(data);
memset(data, 0, sizeof(*data));
}

data->vert_normals = BKE_mesh_vertex_normals_ensure(mesh);

return tree;		return data->tree;
}		}

BVHTree BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh data,		BVHTree BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh data,
struct BMEditMesh *em,		struct BMEditMesh *em,
const int tree_type,		const int tree_type,
const BVHCacheType bvh_cache_type,		const BVHCacheType bvh_cache_type,
BVHCache **bvh_cache_p,		BVHCache **bvh_cache_p,
ThreadMutex *mesh_eval_mutex)		ThreadMutex *mesh_eval_mutex)
{		{
BVHTree *tree = nullptr;		bool lock_started = false;
bool is_cached = false;

memset(data, 0, sizeof(*data));		memset(data, 0, sizeof(*data));
		data->em = em;

if (bvh_cache_p) {		if (bvh_cache_p) {
is_cached = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, nullptr, nullptr);		data->cached = bvhcache_find(
		bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);

if (is_cached && tree == nullptr) {		if (data->cached) {
return tree;		BLI_assert(lock_started == false);
		return data->tree;
}		}
}		}
data->tree = tree;
data->em = em;
data->cached = is_cached;

switch (bvh_cache_type) {		switch (bvh_cache_type) {
case BVHTREE_FROM_EM_VERTS:		case BVHTREE_FROM_EM_VERTS:
if (is_cached == false) {		data->tree = bvhtree_from_editmesh_verts_ex(
tree = bvhtree_from_editmesh_verts_ex(data,		nullptr, em, nullptr, -1, 0.0f, tree_type, 6, lock_started);
em,
nullptr,
-1,
0.0f,
tree_type,
6,
bvh_cache_type,
bvh_cache_p,
mesh_eval_mutex);
}
else {
data->nearest_callback = nullptr;		data->nearest_callback = nullptr;
data->raycast_callback = editmesh_verts_spherecast;		data->raycast_callback = editmesh_verts_spherecast;
}
break;		break;

case BVHTREE_FROM_EM_EDGES:		case BVHTREE_FROM_EM_EDGES:
if (is_cached == false) {		data->tree = bvhtree_from_editmesh_edges_ex(
tree = bvhtree_from_editmesh_edges_ex(data,		nullptr, em, nullptr, -1, 0.0f, tree_type, 6, lock_started);
em,
nullptr,
-1,
0.0f,
tree_type,
6,
bvh_cache_type,
bvh_cache_p,
mesh_eval_mutex);
}
else {
/* Setup #BVHTreeFromMesh */
data->nearest_callback = nullptr; /* TODO */
data->raycast_callback = nullptr; /* TODO */
}
break;		break;

case BVHTREE_FROM_EM_LOOPTRI:		case BVHTREE_FROM_EM_LOOPTRI:
if (is_cached == false) {		data->tree = bvhtree_from_editmesh_looptri_ex(
tree = bvhtree_from_editmesh_looptri_ex(data,		nullptr, em, nullptr, -1, 0.0f, tree_type, 6, lock_started);
em,
nullptr,
-1,
0.0f,
tree_type,
6,
bvh_cache_type,
bvh_cache_p,
mesh_eval_mutex);
}
else {
/* Setup #BVHTreeFromMesh */
data->nearest_callback = editmesh_looptri_nearest_point;		data->nearest_callback = editmesh_looptri_nearest_point;
data->raycast_callback = editmesh_looptri_spherecast;		data->raycast_callback = editmesh_looptri_spherecast;
}
break;		break;
case BVHTREE_FROM_VERTS:		case BVHTREE_FROM_VERTS:
case BVHTREE_FROM_EDGES:		case BVHTREE_FROM_EDGES:
case BVHTREE_FROM_FACES:		case BVHTREE_FROM_FACES:
case BVHTREE_FROM_LOOPTRI:		case BVHTREE_FROM_LOOPTRI:
case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:		case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:
case BVHTREE_FROM_LOOSEVERTS:		case BVHTREE_FROM_LOOSEVERTS:
case BVHTREE_FROM_LOOSEEDGES:		case BVHTREE_FROM_LOOSEEDGES:
case BVHTREE_MAX_ITEM:		case BVHTREE_MAX_ITEM:
BLI_assert(false);		BLI_assert(false);
break;		break;
}		}

if (data->tree != nullptr) {		if (bvh_cache_p) {
		/* Save on cache for later use */
		// printf("BVHTree built and saved on cache\n");
		BLI_assert(data->cached == false);
		data->cached = true;
		bvhcache_insert(*bvh_cache_p, data->tree, bvh_cache_type);
		bvhcache_unlock(*bvh_cache_p, lock_started);
		}

#ifdef DEBUG		#ifdef DEBUG
		if (data->tree) {
if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {		if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {
printf("tree_type %d obtained instead of %d\n",		printf("tree_type %d obtained instead of %d\n",
BLI_bvhtree_get_tree_type(data->tree),		BLI_bvhtree_get_tree_type(data->tree),
tree_type);		tree_type);
}		}
#endif
BLI_assert(data->cached);
}
else {
free_bvhtree_from_editmesh(data);
memset(data, 0, sizeof(*data));
}		}
		#endif

return tree;		return data->tree;
}		}

/** \} */		/** \} */

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name Free Functions		/** \name Free Functions
* \{ */		* \{ */

▲ Show 20 Lines • Show All 72 Lines • Show Last 20 Lines