[Bf-blender-cvs] [ff017df318d] master: Animation: add BKE_fcurve_pathcache_find API
Campbell Barton
noreply at git.blender.org
Fri Mar 26 03:40:05 CET 2021
Commit: ff017df318d5e2dce8c918735e363c0e43458a7c
Author: Campbell Barton
Date: Fri Mar 26 13:08:07 2021 +1100
Branches: master
https://developer.blender.org/rBff017df318d5e2dce8c918735e363c0e43458a7c
Animation: add BKE_fcurve_pathcache_find API
Support a cache for fast RNA path look-ups for RNA-path + index.
Unlike a regular hash lookup, this supports using a single lookup
for the RNA path which is then used to fill an array of F-curves.
Reviewed By: sybren
Ref D10781
===================================================================
M source/blender/blenkernel/BKE_fcurve.h
M source/blender/blenkernel/CMakeLists.txt
A source/blender/blenkernel/intern/fcurve_cache.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_fcurve.h b/source/blender/blenkernel/BKE_fcurve.h
index ad9064fdfde..589d1839dd4 100644
--- a/source/blender/blenkernel/BKE_fcurve.h
+++ b/source/blender/blenkernel/BKE_fcurve.h
@@ -232,6 +232,19 @@ int BKE_fcurve_bezt_binarysearch_index(struct BezTriple array[],
int arraylen,
bool *r_replace);
+/* fcurve_cache.c */
+/* Cached f-curve look-ups, use when this needs to be done many times. */
+struct FCurvePathCache;
+struct FCurvePathCache *BKE_fcurve_pathcache_create(ListBase *list);
+void BKE_fcurve_pathcache_destroy(struct FCurvePathCache *fcache);
+struct FCurve *BKE_fcurve_pathcache_find(struct FCurvePathCache *fcache,
+ const char rna_path[],
+ const int array_index);
+int BKE_fcurve_pathcache_find_array(struct FCurvePathCache *fcache,
+ const char *rna_path,
+ struct FCurve **fcurve_result,
+ int fcurve_result_len);
+
/* get the time extents for F-Curve */
bool BKE_fcurve_calc_range(
struct FCurve *fcu, float *min, float *max, const bool do_sel_only, const bool do_min_length);
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 5ccaefe6f6f..12a801545a9 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -126,6 +126,7 @@ set(SRC
intern/editmesh_tangent.c
intern/effect.c
intern/fcurve.c
+ intern/fcurve_cache.c
intern/fcurve_driver.c
intern/fluid.c
intern/fmodifier.c
diff --git a/source/blender/blenkernel/intern/fcurve_cache.c b/source/blender/blenkernel/intern/fcurve_cache.c
new file mode 100644
index 00000000000..8142b871edd
--- /dev/null
+++ b/source/blender/blenkernel/intern/fcurve_cache.c
@@ -0,0 +1,189 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bke
+ *
+ * Cache F-Curve look-ups.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_anim_types.h"
+
+#include "BLI_ghash.h"
+#include "BLI_listbase.h"
+
+#include "BKE_fcurve.h"
+
+/* -------------------------------------------------------------------- */
+/** \name F-Curve Path Cache
+ *
+ * Cache for finding curves by RNA path & array index.
+ * \{ */
+
+struct FCurvePathCache_Span {
+ /** Index in the #FCurvePathCache.fcurve_array indicating the start of the span. */
+ uint index;
+ /** Number of items in the span in #FCurvePathCache.fcurve_array that share an RNA path. */
+ uint len;
+};
+
+struct FCurvePathCache {
+ /** All curves sorted by (#FCurve.rna_path, #FCurve.array_index) */
+ FCurve **fcurve_array;
+ uint fcurve_array_len;
+ /** Storage for values of `span_from_rna_path`. */
+ struct FCurvePathCache_Span *span_table;
+ /** Map `FCurve.rna_path` to elements in #FCurvePathCache.span_table */
+ GHash *span_from_rna_path;
+};
+
+/**
+ * #qsort callback for an #FCurve array.
+ */
+static int fcurve_cmp_for_cache(const void *fcu_a_p, const void *fcu_b_p)
+{
+ const FCurve *fcu_a = *((const FCurve **)fcu_a_p);
+ const FCurve *fcu_b = *((const FCurve **)fcu_b_p);
+ const int cmp = strcmp(fcu_a->rna_path, fcu_b->rna_path);
+ if (cmp != 0) {
+ return cmp;
+ }
+ if (fcu_a->array_index < fcu_b->array_index) {
+ return -1;
+ }
+ if (fcu_a->array_index > fcu_b->array_index) {
+ return 1;
+ }
+ return 0;
+}
+
+struct FCurvePathCache *BKE_fcurve_pathcache_create(ListBase *list)
+{
+ const uint fcurve_array_len = BLI_listbase_count(list);
+ FCurve **fcurve_array = MEM_mallocN(sizeof(*fcurve_array) * fcurve_array_len, __func__);
+ uint i;
+ LISTBASE_FOREACH_INDEX (FCurve *, fcu, list, i) {
+ fcurve_array[i] = fcu;
+ }
+ qsort(fcurve_array, fcurve_array_len, sizeof(FCurve *), fcurve_cmp_for_cache);
+
+ /* Allow for the case no F-curves share an RNA-path, otherwise this is over-allocated.
+ * Although in practice it's likely to only be 3-4x as large as is needed
+ * (with transform channels for e.g.). */
+ struct FCurvePathCache_Span *span_table = MEM_mallocN(sizeof(*span_table) * fcurve_array_len,
+ __func__);
+
+ /* May over reserve, harmless. */
+ GHash *span_from_rna_path = BLI_ghash_str_new_ex(__func__, fcurve_array_len);
+ uint span_index = 0;
+ i = 0;
+ while (i < fcurve_array_len) {
+ uint i_end;
+ for (i_end = i + 1; i_end < fcurve_array_len; i_end++) {
+ /* As the indices are sorted, we know a decrease means a new RNA path is found. */
+ if (fcurve_array[i]->array_index > fcurve_array[i_end]->array_index) {
+ BLI_assert(!STREQ(fcurve_array[i]->rna_path, fcurve_array[i_end]->rna_path));
+ break;
+ }
+ if (!STREQ(fcurve_array[i]->rna_path, fcurve_array[i_end]->rna_path)) {
+ break;
+ }
+ }
+
+ struct FCurvePathCache_Span *span = &span_table[span_index++];
+ span->index = i;
+ span->len = i_end - i;
+ BLI_ghash_insert(span_from_rna_path, fcurve_array[i]->rna_path, span);
+ i = i_end;
+ }
+
+ struct FCurvePathCache *fcache = MEM_callocN(sizeof(struct FCurvePathCache), __func__);
+ fcache->fcurve_array = fcurve_array;
+ fcache->fcurve_array_len = fcurve_array_len;
+ fcache->span_table = span_table;
+ fcache->span_from_rna_path = span_from_rna_path;
+
+ return fcache;
+}
+
+void BKE_fcurve_pathcache_destroy(struct FCurvePathCache *fcache)
+{
+ MEM_freeN(fcache->fcurve_array);
+ MEM_freeN(fcache->span_table);
+ BLI_ghash_free(fcache->span_from_rna_path, NULL, NULL);
+ MEM_freeN(fcache);
+}
+
+FCurve *BKE_fcurve_pathcache_find(struct FCurvePathCache *fcache,
+ const char *rna_path,
+ const int array_index)
+{
+ const struct FCurvePathCache_Span *span = BLI_ghash_lookup(fcache->span_from_rna_path, rna_path);
+ if (span == NULL) {
+ return NULL;
+ }
+
+ FCurve **fcurve = fcache->fcurve_array + span->index;
+ const uint len = span->len;
+ for (int i = 0; i < len; i++) {
+ if (fcurve[i]->array_index == array_index) {
+ return fcurve[i];
+ }
+ /* As these are sorted, early exit. */
+ if (fcurve[i]->array_index > array_index) {
+ break;
+ }
+ }
+ return NULL;
+}
+
+/**
+ * Fill in an array of F-Curve, leave NULL when not found.
+ *
+ * \return The number of F-Curves found.
+ */
+int BKE_fcurve_pathcache_find_array(struct FCurvePathCache *fcache,
+ const char *rna_path,
+ FCurve **fcurve_result,
+ int fcurve_result_len)
+{
+ memset(fcurve_result, 0x0, sizeof(*fcurve_result) * fcurve_result_len);
+
+ const struct FCurvePathCache_Span *span = BLI_ghash_lookup(fcache->span_from_rna_path, rna_path);
+ if (span == NULL) {
+ return 0;
+ }
+
+ int found = 0;
+ FCurve **fcurve = fcache->fcurve_array + span->index;
+ const uint len = span->len;
+ for (int i = 0; i < len; i++) {
+ /* As these are sorted, early exit. */
+ if ((uint)fcurve[i]->array_index > (uint)fcurve_result_len) {
+ break;
+ }
+ fcurve_result[fcurve[i]->array_index] = fcurve[i];
+ found += 1;
+ }
+ return found;
+}
+
+/** \} */
More information about the Bf-blender-cvs
mailing list