[Bf-blender-cvs] [39b525e0f07] master: Fix T78296: Performance - Use Binary Search for MDeformWeight
Jeroen Bakker
noreply at git.blender.org
Fri Jul 10 12:10:25 CEST 2020
Commit: 39b525e0f07fa25dcda54226ade789959b642dec
Author: Jeroen Bakker
Date: Fri Jul 10 12:05:31 2020 +0200
Branches: master
https://developer.blender.org/rB39b525e0f07fa25dcda54226ade789959b642dec
Fix T78296: Performance - Use Binary Search for MDeformWeight
Use binary search for querying deform weights.
Spring 02_020_A.anim.blend on Ryzen 1700X goes from 12.4 to 12.7fps.
During profiling it was detected that adding new items to the head was faster than adding to the tail.
Reviewed By: Campbell Barton
Differential Revision: https://developer.blender.org/D8127
===================================================================
M source/blender/blenkernel/BKE_blender_version.h
M source/blender/blenkernel/BKE_deform.h
M source/blender/blenkernel/intern/customdata.c
M source/blender/blenkernel/intern/deform.c
M source/blender/blenkernel/intern/object_deform.c
M source/blender/blenloader/intern/versioning_290.c
M source/blender/blenloader/intern/writefile.c
M source/blender/editors/gpencil/gpencil_data.c
M source/blender/makesdna/DNA_meshdata_types.h
===================================================================
diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h
index 57f22a8d709..556c1c961dc 100644
--- a/source/blender/blenkernel/BKE_blender_version.h
+++ b/source/blender/blenkernel/BKE_blender_version.h
@@ -40,7 +40,7 @@ extern "C" {
/* Blender file format version. */
#define BLENDER_FILE_VERSION BLENDER_VERSION
-#define BLENDER_FILE_SUBVERSION 6
+#define BLENDER_FILE_SUBVERSION 7
/* Minimum Blender version that supports reading file written with the current
* version. Older Blender versions will test this and show a warning if the file
diff --git a/source/blender/blenkernel/BKE_deform.h b/source/blender/blenkernel/BKE_deform.h
index 04b85aebb39..b5a7df9ff57 100644
--- a/source/blender/blenkernel/BKE_deform.h
+++ b/source/blender/blenkernel/BKE_deform.h
@@ -54,6 +54,7 @@ void BKE_object_defgroup_unique_name(struct bDeformGroup *dg, struct Object *ob)
struct MDeformWeight *BKE_defvert_find_index(const struct MDeformVert *dv, const int defgroup);
struct MDeformWeight *BKE_defvert_ensure_index(struct MDeformVert *dv, const int defgroup);
+void BKE_defvert_array_sort_weights(struct MDeformVert *dv, const int num_verts);
void BKE_defvert_add_index_notest(struct MDeformVert *dv, int defgroup, const float weight);
void BKE_defvert_remove_group(struct MDeformVert *dvert, struct MDeformWeight *dw);
void BKE_defvert_clear(struct MDeformVert *dvert);
@@ -163,6 +164,16 @@ void BKE_defvert_extract_vgroup_to_polyweights(struct MDeformVert *dvert,
void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight);
+#ifndef NDEBUG
+bool BKE_defvert_is_sorted_for_assert(const struct MDeformVert *dv);
+# define BKE_DEFVERT_IS_SORTED_ASSERT(dv) BLI_assert(BKE_defvert_is_sorted_for_assert(dv))
+#else
+# define BKE_DEFVERT_IS_SORTED_ASSERT(dv) \
+ if (false) { \
+ (void)(dv); \
+ }
+#endif
+
#ifdef __cplusplus
}
#endif
diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c
index c11fa69db76..6843c4c58fa 100644
--- a/source/blender/blenkernel/intern/customdata.c
+++ b/source/blender/blenkernel/intern/customdata.c
@@ -47,6 +47,7 @@
#include "BKE_customdata.h"
#include "BKE_customdata_file.h"
+#include "BKE_deform.h"
#include "BKE_main.h"
#include "BKE_mesh_mapping.h"
#include "BKE_mesh_remap.h"
@@ -320,6 +321,7 @@ static void layerInterp_mdeformvert(const void **sources,
}
dvert->dw[i] = node->dw;
}
+ BKE_defvert_array_sort_weights(dvert, count);
}
else {
memset(dvert, 0, sizeof(*dvert));
diff --git a/source/blender/blenkernel/intern/deform.c b/source/blender/blenkernel/intern/deform.c
index b97935d57f2..7e924db5ae4 100644
--- a/source/blender/blenkernel/intern/deform.c
+++ b/source/blender/blenkernel/intern/deform.c
@@ -216,6 +216,47 @@ void BKE_defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, cons
}
}
+/* -------------------------------------------------------------------- */
+/** \name Deform Weights - Sorting
+ *
+ * \{ */
+
+/* Reorder the weights so they are sorted. It is required that all `MDeformVert` weights are sorted
+ * so we can use binary search.
+ */
+static int defweight_cmp(const void *a, const void *b)
+{
+ const MDeformWeight *dw1 = a;
+ const MDeformWeight *dw2 = b;
+ if (dw1->def_nr < dw2->def_nr) {
+ return -1;
+ }
+ else if (dw1->def_nr > dw2->def_nr) {
+ return 1;
+ }
+ else {
+ return 0;
+ }
+}
+
+static void defvert_sort_weights(struct MDeformVert *dvert)
+{
+ if (dvert->dw) {
+ qsort(dvert->dw, dvert->totweight, sizeof(MDeformWeight), defweight_cmp);
+ }
+}
+
+void BKE_defvert_array_sort_weights(struct MDeformVert *dvert, const int num_verts)
+{
+ if (!dvert) {
+ return;
+ }
+ for (int i = 0; i < num_verts; i++) {
+ defvert_sort_weights(&dvert[i]);
+ }
+}
+/* \} */
+
/**
* be sure all flip_map values are valid
*/
@@ -260,6 +301,7 @@ void BKE_defvert_remap(MDeformVert *dvert, int *map, const int map_len)
dw->def_nr = map[dw->def_nr];
}
}
+ defvert_sort_weights(dvert);
}
/**
@@ -459,6 +501,7 @@ void BKE_defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_ma
}
}
}
+ defvert_sort_weights(dvert);
}
void BKE_defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
@@ -665,23 +708,40 @@ float BKE_defvert_array_find_weight_safe(const struct MDeformVert *dvert,
return BKE_defvert_find_weight(dvert + index, defgroup);
}
+static int defvert_index_get(const MDeformVert *dvert, const int defgroup)
+{
+ int low = 0;
+ int high = dvert->totweight - 1;
+ int mid;
+ while (low < high) {
+ mid = (low + high) / 2;
+ MDeformWeight *dweight = &dvert->dw[mid];
+ const unsigned int dweight_def_nr = dweight->def_nr;
+ if (dweight_def_nr == defgroup) {
+ return mid;
+ }
+ if (dweight_def_nr < defgroup) {
+ low = mid + 1;
+ }
+ else {
+ high = mid - 1;
+ }
+ }
+ return -1;
+}
+
MDeformWeight *BKE_defvert_find_index(const MDeformVert *dvert, const int defgroup)
{
- if (dvert && defgroup >= 0) {
- MDeformWeight *dw = dvert->dw;
- unsigned int i;
+ BLI_assert(dvert);
+ BLI_assert(defgroup >= 0);
- for (i = dvert->totweight; i != 0; i--, dw++) {
- if (dw->def_nr == defgroup) {
- return dw;
- }
- }
+ int index = defvert_index_get(dvert, defgroup);
+ if (index == -1) {
+ return NULL;
}
else {
- BLI_assert(0);
+ return &dvert->dw[index];
}
-
- return NULL;
}
/**
@@ -706,17 +766,18 @@ MDeformWeight *BKE_defvert_ensure_index(MDeformVert *dvert, const int defgroup)
dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
if (dvert->dw) {
- memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
+ memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
MEM_freeN(dvert->dw);
}
dvert->dw = dw_new;
- dw_new += dvert->totweight;
dw_new->weight = 0.0f;
dw_new->def_nr = defgroup;
/* Group index */
dvert->totweight++;
+ defvert_sort_weights(dvert);
+
return dw_new;
}
@@ -740,14 +801,15 @@ void BKE_defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float
dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1),
"defvert_add_to group, new deformWeight");
if (dvert->dw) {
- memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
+ memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
MEM_freeN(dvert->dw);
}
dvert->dw = dw_new;
- dw_new += dvert->totweight;
dw_new->weight = weight;
dw_new->def_nr = defgroup;
dvert->totweight++;
+
+ defvert_sort_weights(dvert);
}
/**
@@ -773,7 +835,7 @@ void BKE_defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
BLI_assert(dvert->dw != NULL);
if (i != dvert->totweight) {
- dvert->dw[i] = dvert->dw[dvert->totweight];
+ memmove(&dvert->dw[i], &dvert->dw[i + 1], sizeof(MDeformWeight) * dvert->totweight - i);
}
dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
@@ -1525,4 +1587,17 @@ void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight)
}
}
+#ifndef NDEBUG
+bool BKE_defvert_is_sorted_for_assert(const MDeformVert *dv)
+{
+ const MDeformWeight *dw = dv->dw;
+ for (int i = 1; i < dv->totweight; i++) {
+ if (dw[i - 1].def_nr > dw[i].def_nr) {
+ return false;
+ }
+ }
+ return true;
+}
+#endif
+
/** \} */
diff --git a/source/blender/blenkernel/intern/object_deform.c b/source/blender/blenkernel/intern/object_deform.c
index 6ca1442497a..f7d22f300ef 100644
--- a/source/blender/blenkernel/intern/object_deform.c
+++ b/source/blender/blenkernel/intern/object_deform.c
@@ -534,6 +534,7 @@ void BKE_object_defgroup_index_map_apply(MDeformVert *dvert,
dv->totweight = totweight;
}
}
+ BKE_defvert_array_sort_weights(dv, dvert_len);
}
/**
diff --git a/source/blender/blenloader/intern/versioning_290.c b/source/blender/blenloader/intern/versioning_290.c
index 0d16b58d28f..a99da5eb333 100644
--- a/source/blender/blenloader/intern/versioning_290.c
+++ b/source/blender/blenloader/intern/versioning_290.c
@@ -27,6 +27,9 @@
#include "DNA_constraint_types.h"
#include "DNA_genfile.h"
#include "DNA_gpencil_modifier_types.h"
+#include "DNA_gpencil_types.h"
+#include "DNA_lattice_types.h"
+#include "DNA_mesh_types.h"
#include "DNA_modifier_types.h"
#include "DNA_object_types.h"
#include "DNA_screen_types.h"
@@ -34,6 +37,7 @@
#include "BKE_collection.h"
#include "BKE_colortools.h"
+#include "BKE_deform.h"
#include "BKE_lib_id.h"
#include "BKE_main.h"
@@ -354,6 +358,26 @@ void blo_do_versions_290(FileData *fd, Library *UNUSED(lib), Main *bmain)
}
}
+ /* Make sure that all weights of MDeformVert are sorted. */
+ if (!MAIN_VERSION_ATLEAST(bmain, 290, 7)) {
+ for (Mesh *mesh = bmain->meshes.first; mesh != NULL; mesh = mesh->id.next) {
+ BKE_defvert_array_sort_weights(mesh->dvert, mesh->totvert);
+ }
+ for (Lattice *lt = bmain->lattices.first; lt != NULL; lt = lt->id.next) {
+ const int totvert = lt->pntsu * lt->pntsv * lt->pntsw;
+ BKE_defvert_array_sort_weights(lt->dvert, totvert);
+ }
+ for (bGPdata *gp = bmain->gpencils.first; gp != NULL; gp = gp->id.next) {
+ LISTBASE_FOREACH (bGPDlayer *, layer, &gp->layers) {
+ LISTBASE_FOREACH (bGPDframe *, frame, &layer->frames) {
+ LISTBASE_FOREACH (bGPDstroke *, stroke, &frame->strokes) {
+ BKE_defvert_array_sort_weights(stroke->dvert, stroke->totpoints);
+ }
+ }
+ }
+ }
+ }
+
/**
* Versioning code until next subversion bump goes here.
*
diff --git a/source/blender/blenloader/intern/writefile.c b/source/blender/blenloader/intern/writefile.c
index 4e2b4fef9a0..29461298cea 100644
--- a/source/blender/blenloader/intern/writefile.c
+++ b/source/blender/blenloader/intern/writefile.c
@@ -159,6 +159,7 @@
#include "BKE_constraint.h"
#include "BKE_curve.h"
#include "BKE_curveprofile.h"
+#include "BKE_deform.h"
#include "BKE_fcurve.h"
#include
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list