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. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org https://lists.blender.org/mailman/listinfo/bf-blender-cvs