[Bf-blender-cvs] [752139556f5] master: BVHCache: Performance
Jeroen Bakker
noreply at git.blender.org
Tue Jun 2 16:01:53 CEST 2020
Commit: 752139556f58988d8717e12f6288fdce7eedd2ce
Author: Jeroen Bakker
Date: Tue Jun 2 15:59:30 2020 +0200
Branches: master
https://developer.blender.org/rB752139556f58988d8717e12f6288fdce7eedd2ce
BVHCache: Performance
This patch changes the BVHCache implementation. It will use
a primitive array in stead of the ListBase. The locking is also
changed from a global lock to a per cache instance lock.
The performance of `gabby.blend` available on the cloud increased from 9.7
fps to 10.5 fps.
Reviewed By: Brecht van Lommel
Differential Revision: https://developer.blender.org/D7817
===================================================================
M source/blender/blenkernel/BKE_bvhutils.h
M source/blender/blenkernel/intern/bvhutils.c
M source/blender/blenkernel/intern/mesh_remap.c
M source/blender/blenkernel/intern/mesh_runtime.c
M source/blender/editors/transform/transform_snap_object.c
M source/blender/makesdna/DNA_mesh_types.h
M source/blender/modifiers/intern/MOD_weld.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index 458f1ab7a56..5d7e8fe743e 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -25,6 +25,7 @@
#include "BLI_bitmap.h"
#include "BLI_kdopbvh.h"
+#include "BLI_threads.h"
#ifdef __cplusplus
extern "C" {
@@ -39,7 +40,7 @@ struct MFace;
struct MVert;
struct Mesh;
-typedef struct LinkNode BVHCache;
+struct BVHCache;
/**
* Struct that stores basic information about a BVHTree built from a edit-mesh.
@@ -98,6 +99,9 @@ typedef enum BVHCacheType {
BVHTREE_FROM_EM_VERTS,
BVHTREE_FROM_EM_EDGES,
BVHTREE_FROM_EM_LOOPTRI,
+
+ /* Keep `BVHTREE_MAX_ITEM` as last item. */
+ BVHTREE_MAX_ITEM,
} BVHCacheType;
/**
@@ -122,7 +126,8 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data,
const struct MVert *vert,
@@ -134,7 +139,8 @@ BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *bvhtree_from_editmesh_edges(
BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
@@ -147,7 +153,8 @@ BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *bvhtree_from_mesh_edges_ex(struct BVHTreeFromMesh *data,
const struct MVert *vert,
@@ -161,7 +168,8 @@ BVHTree *bvhtree_from_mesh_edges_ex(struct BVHTreeFromMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data,
const struct MVert *vert,
@@ -175,7 +183,8 @@ BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *bvhtree_from_editmesh_looptri(
BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
@@ -188,7 +197,8 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *bvhtree_from_mesh_looptri_ex(struct BVHTreeFromMesh *data,
const struct MVert *vert,
@@ -204,7 +214,8 @@ BVHTree *bvhtree_from_mesh_looptri_ex(struct BVHTreeFromMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
struct Mesh *mesh,
@@ -215,7 +226,8 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
struct BMEditMesh *em,
const int tree_type,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache);
+ struct BVHCache **bvh_cache_p,
+ ThreadMutex *mesh_eval_mutex);
/**
* Frees data allocated by a call to bvhtree_from_mesh_*.
@@ -244,10 +256,9 @@ float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray,
/* Using local coordinates */
-bool bvhcache_find(const BVHCache *cache, BVHCacheType type, BVHTree **r_tree);
-bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree);
-void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, BVHCacheType type);
-void bvhcache_free(BVHCache **cache_p);
+bool bvhcache_has_tree(const struct BVHCache *bvh_cache, const BVHTree *tree);
+struct BVHCache *bvhcache_init(void);
+void bvhcache_free(struct BVHCache *bvh_cache);
#ifdef __cplusplus
}
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index cd90ebc2eed..93794eb9709 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -41,8 +41,126 @@
#include "MEM_guardedalloc.h"
-static ThreadRWMutex cache_rwlock = BLI_RWLOCK_INITIALIZER;
+/* -------------------------------------------------------------------- */
+/** \name BVHCache
+ * \{ */
+
+typedef struct BVHCacheItem {
+ bool is_filled;
+ BVHTree *tree;
+} BVHCacheItem;
+
+typedef struct BVHCache {
+ BVHCacheItem items[BVHTREE_MAX_ITEM];
+ ThreadMutex mutex;
+} BVHCache;
+
+/**
+ * Queries a bvhcache for the cache bvhtree of the request type
+ *
+ * When the `r_locked` is filled and the tree could not be found the caches mutex will be
+ * locked. This mutex can be unlocked by calling `bvhcache_unlock`.
+ *
+ * When `r_locked` is used the `mesh_eval_mutex` must contain the `Mesh_Runtime.eval_mutex`.
+ */
+static bool bvhcache_find(BVHCache **bvh_cache_p,
+ BVHCacheType type,
+ BVHTree **r_tree,
+ bool *r_locked,
+ ThreadMutex *mesh_eval_mutex)
+{
+ bool do_lock = r_locked;
+ if (r_locked) {
+ *r_locked = false;
+ }
+ if (*bvh_cache_p == NULL) {
+ if (!do_lock) {
+ /* Cache does not exist and no lock is requested. */
+ return false;
+ }
+ /* Lazy initialization of the bvh_cache using the `mesh_eval_mutex`. */
+ BLI_mutex_lock(mesh_eval_mutex);
+ if (*bvh_cache_p == NULL) {
+ *bvh_cache_p = bvhcache_init();
+ }
+ BLI_mutex_unlock(mesh_eval_mutex);
+ }
+ BVHCache *bvh_cache = *bvh_cache_p;
+ if (bvh_cache->items[type].is_filled) {
+ *r_tree = bvh_cache->items[type].tree;
+ return true;
+ }
+ if (do_lock) {
+ BLI_mutex_lock(&bvh_cache->mutex);
+ bool in_cache = bvhcache_find(bvh_cache_p, type, r_tree, NULL, NULL);
+ if (in_cache) {
+ BLI_mutex_unlock(&bvh_cache->mutex);
+ return in_cache;
+ }
+ *r_locked = true;
+ }
+ return false;
+}
+
+static void bvhcache_unlock(BVHCache *bvh_cache, bool lock_started)
+{
+ if (lock_started) {
+ BLI_mutex_unlock(&bvh_cache->mutex);
+ }
+}
+
+bool bvhcache_has_tree(const BVHCache *bvh_cache, const BVHTree *tree)
+{
+ if (bvh_cache == NULL) {
+ return false;
+ }
+
+ for (BVHCacheType i = 0; i < BVHTREE_MAX_ITEM; i++) {
+ if (bvh_cache->items[i].tree == tree) {
+ return true;
+ }
+ }
+ return false;
+}
+
+BVHCache *bvhcache_init(void)
+{
+ BVHCache *cache = MEM_callocN(sizeof(BVHCache), __func__);
+ BLI_mutex_init(&cache->mutex);
+ return cache;
+}
+/**
+ * Inserts a BVHTree of the given type under the cache
+ * After that the caller no longer needs to worry when to free the BVHTree
+ * as that will be done when the cache is freed.
+ *
+ * A call to this assumes that there was no previous cached tree of the given type
+ * \warning The #BVHTree can be NULL.
+ */
+static void bvhcache_insert(BVHCache *bvh_cache, BVHTree *tree, BVHCacheType type)
+{
+ BVHCacheItem *item = &bvh_cache->items[type];
+ BLI_assert(!item->is_filled);
+ item->tree = tree;
+ item->is_filled = true;
+}
+
+/**
+ * frees a bvhcache
+ */
+void bvhcache_free(BVHCache *bvh_cache)
+{
+ for (BVHCacheType index = 0; index < BVHTREE_MAX_ITEM; index++) {
+ BVHCacheItem *item = &bvh_cache->items[index];
+ BLI_bvhtree_free(item->tree);
+ item->tree = NULL;
+ }
+ BLI_mutex_end(&bvh_cache->mutex);
+ MEM_freeN(bvh_cache);
+}
+
+/** \} */
/* -------------------------------------------------------------------- */
/** \name Local Callbacks
* \{ */
@@ -518,29 +636,26 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
int tree_type,
int axis,
const BVHCacheType bvh_cache_type,
- BVHCache **bvh_cache)
+ BVHCache **bvh_cache_p,
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list