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

2 files changed, 26 insertions, 0 deletions

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 "BKE_fcurve_driver.h"
 #include "BKE_global.h"  // for G
@@ -2044,6 +2045,7 @@ static void write_dverts(BlendWriter *writer, int count, MDeformVert *dvlist)
     /* Write deformation data for each dvert */
     for (int i = 0; i < count; i++) {
       if (dvlist[i].dw) {
+        BKE_DEFVERT_IS_SORTED_ASSERT(&dvlist[i]);
         BLO_write_struct_array(writer, MDeformWeight, dvlist[i].totweight, dvlist[i].dw);
       }
     }