Surface Deform: support sparse binding mode for improving performance.

When a vertex group is used to limit the influence of the modifier
to a subset of vertices, binding data for vertices with zero weight
is not needed. This wastes memory, disk space and CPU cycles.

If the vertex group contents is known to be final and constant,
it is reasonable to optimize by only storing data group vertices.
This has to be an option in case the group can change.

Supporting this requires adding a vertex index field and spliting
the vertex count into mesh and bind variants, but both happen to
fit in available padding. The old numverts field is renamed to the
new bound vertex count field to maintain the array length invariant.
Versioning is used to initialize the other new fields.

If a file with sparse binding is opened in an old blender version,
it is corrupted into a non-sparse bind with vertex count mismatch,
preventing the modifier from working until rebind.

Differential Revision: https://developer.blender.org/D11924

6 files changed, 121 insertions, 22 deletions

diff --git a/source/blender/blenloader/intern/versioning_300.c b/source/blender/blenloader/intern/versioning_300.c
index d36c622c572..313ce734bbc 100644
--- a/source/blender/blenloader/intern/versioning_300.c
+++ b/source/blender/blenloader/intern/versioning_300.c
@@ -551,5 +551,24 @@ void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
    */
   {
     /* Keep this block, even when empty. */
+
+    /* Convert Surface Deform to sparse-capable bind structure. */
+    if (!DNA_struct_elem_find(
+            fd->filesdna, "SurfaceDeformModifierData", "int", "num_mesh_verts")) {
+      LISTBASE_FOREACH (Object *, ob, &bmain->objects) {
+        LISTBASE_FOREACH (ModifierData *, md, &ob->modifiers) {
+          if (md->type == eModifierType_SurfaceDeform) {
+            SurfaceDeformModifierData *smd = (SurfaceDeformModifierData *)md;
+            if (smd->num_bind_verts && smd->verts) {
+              smd->num_mesh_verts = smd->num_bind_verts;
+
+              for (unsigned int i = 0; i < smd->num_bind_verts; i++) {
+                smd->verts[i].vertex_idx = i;
+              }
+            }
+          }
+        }
+      }
+    }
   }
 }
diff --git a/source/blender/makesdna/DNA_modifier_defaults.h b/source/blender/makesdna/DNA_modifier_defaults.h
index f6dac88051b..1b3dbd148df 100644
--- a/source/blender/makesdna/DNA_modifier_defaults.h
+++ b/source/blender/makesdna/DNA_modifier_defaults.h
@@ -647,7 +647,8 @@
     .target = NULL, \
     .verts = NULL, \
     .falloff = 4.0f, \
-    .numverts = 0, \
+    .num_mesh_verts = 0, \
+    .num_bind_verts = 0, \
     .numpoly = 0, \
     .flags = 0, \
     .mat = _DNA_DEFAULT_UNIT_M4, \
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 1c765d19ce2..401b49f2ee8 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -2180,7 +2180,7 @@ typedef struct SDefBind {
 typedef struct SDefVert {
   SDefBind *binds;
   unsigned int numbinds;
-  char _pad[4];
+  unsigned int vertex_idx;
 } SDefVert;
 
 typedef struct SurfaceDeformModifierData {
@@ -2192,11 +2192,10 @@ typedef struct SurfaceDeformModifierData {
   /** Vertex bind data. */
   SDefVert *verts;
   float falloff;
-  unsigned int numverts, numpoly;
+  unsigned int num_mesh_verts, num_bind_verts, numpoly;
   int flags;
   float mat[4][4];
   float strength;
-  char _pad[4];
   char defgrp_name[64];
 } SurfaceDeformModifierData;
 
@@ -2204,10 +2203,9 @@ typedef struct SurfaceDeformModifierData {
 enum {
   /* This indicates "do bind on next modifier evaluation" as well as "is bound". */
   MOD_SDEF_BIND = (1 << 0),
-  MOD_SDEF_INVERT_VGROUP = (1 << 1)
-
-  /* MOD_SDEF_USES_LOOPTRI = (1 << 1), */ /* UNUSED */
-  /* MOD_SDEF_HAS_CONCAVE = (1 << 2), */  /* UNUSED */
+  MOD_SDEF_INVERT_VGROUP = (1 << 1),
+  /* Only store bind data for nonzero vgroup weights at the time of bind. */
+  MOD_SDEF_SPARSE_BIND = (1 << 2),
 };
 
 /* Surface Deform vertex bind modes */
diff --git a/source/blender/makesdna/intern/dna_rename_defs.h b/source/blender/makesdna/intern/dna_rename_defs.h
index 735be0c10bf..d363e40e4f0 100644
--- a/source/blender/makesdna/intern/dna_rename_defs.h
+++ b/source/blender/makesdna/intern/dna_rename_defs.h
@@ -136,4 +136,5 @@ DNA_STRUCT_RENAME_ELEM(wmWindow, global_area_map, global_areas)
 DNA_STRUCT_RENAME_ELEM(LineartGpencilModifierData, line_types, edge_types)
 DNA_STRUCT_RENAME_ELEM(LineartGpencilModifierData, transparency_flags, mask_switches)
 DNA_STRUCT_RENAME_ELEM(LineartGpencilModifierData, transparency_mask, material_mask_bits)
+DNA_STRUCT_RENAME_ELEM(SurfaceDeformModifierData, numverts, num_bind_verts)
 DNA_STRUCT_RENAME_ELEM(MaterialLineArt, transparency_mask, material_mask_bits)
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index e64eaf8c363..5fddb0f18a5 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -6884,6 +6884,15 @@ static void rna_def_modifier_surfacedeform(BlenderRNA *brna)
   RNA_def_property_ui_text(prop, "Invert", "Invert vertex group influence");
   RNA_def_property_update(prop, 0, "rna_Modifier_update");
 
+  prop = RNA_def_property(srna, "use_sparse_bind", PROP_BOOLEAN, PROP_NONE);
+  RNA_def_property_boolean_sdna(prop, NULL, "flags", MOD_SDEF_SPARSE_BIND);
+  RNA_def_property_clear_flag(prop, PROP_ANIMATABLE);
+  RNA_def_property_ui_text(
+      prop,
+      "Sparse Bind",
+      "Only record binding data for vertices matching the vertex group at the time of bind");
+  RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
   prop = RNA_def_property(srna, "strength", PROP_FLOAT, PROP_NONE);
   RNA_def_property_range(prop, -100, 100);
   RNA_def_property_ui_range(prop, -100, 100, 10, 2);
diff --git a/source/blender/modifiers/intern/MOD_surfacedeform.c b/source/blender/modifiers/intern/MOD_surfacedeform.c
index dd011a293ee..ec6de8f8387 100644
--- a/source/blender/modifiers/intern/MOD_surfacedeform.c
+++ b/source/blender/modifiers/intern/MOD_surfacedeform.c
@@ -94,6 +94,11 @@ typedef struct SDefBindCalcData {
   float imat[4][4];
   const float falloff;
   int success;
+  /** Vertex group lookup data. */
+  const MDeformVert *const dvert;
+  int const defgrp_index;
+  bool const invert_vgroup;
+  bool const sparse_bind;
 } SDefBindCalcData;
 
 /**
@@ -218,7 +223,7 @@ static void freeData(ModifierData *md)
   SurfaceDeformModifierData *smd = (SurfaceDeformModifierData *)md;
 
   if (smd->verts) {
-    for (int i = 0; i < smd->numverts; i++) {
+    for (int i = 0; i < smd->num_bind_verts; i++) {
       if (smd->verts[i].binds) {
         for (int j = 0; j < smd->verts[i].numbinds; j++) {
           MEM_SAFE_FREE(smd->verts[i].binds[j].vert_inds);
@@ -243,7 +248,7 @@ static void copyData(const ModifierData *md, ModifierData *target, const int fla
   if (smd->verts) {
     tsmd->verts = MEM_dupallocN(smd->verts);
 
-    for (int i = 0; i < smd->numverts; i++) {
+    for (int i = 0; i < smd->num_bind_verts; i++) {
       if (smd->verts[i].binds) {
         tsmd->verts[i].binds = MEM_dupallocN(smd->verts[i].binds);
 
@@ -963,12 +968,32 @@ static void bindVert(void *__restrict userdata,
   SDefBindPoly *bpoly;
   SDefBind *sdbind;
 
+  sdvert->vertex_idx = index;
+
   if (data->success != MOD_SDEF_BIND_RESULT_SUCCESS) {
     sdvert->binds = NULL;
     sdvert->numbinds = 0;
     return;
   }
 
+  if (data->sparse_bind) {
+    float weight = 0.0f;
+
+    if (data->dvert && data->defgrp_index != -1) {
+      weight = BKE_defvert_find_weight(&data->dvert[index], data->defgrp_index);
+    }
+
+    if (data->invert_vgroup) {
+      weight = 1.0f - weight;
+    }
+
+    if (weight <= 0) {
+      sdvert->binds = NULL;
+      sdvert->numbinds = 0;
+      return;
+    }
+  }
+
   copy_v3_v3(point_co, data->vertexCos[index]);
   bwdata = computeBindWeights(data, point_co);
 
@@ -1135,6 +1160,21 @@ static void bindVert(void *__restrict userdata,
   freeBindData(bwdata);
 }
 
+/* Remove vertices without bind data from the bind array. */
+static void compactSparseBinds(SurfaceDeformModifierData *smd)
+{
+  smd->num_bind_verts = 0;
+
+  for (uint i = 0; i < smd->num_mesh_verts; i++) {
+    if (smd->verts[i].numbinds > 0) {
+      smd->verts[smd->num_bind_verts++] = smd->verts[i];
+    }
+  }
+
+  smd->verts = MEM_reallocN_id(
+      smd->verts, sizeof(*smd->verts) * smd->num_bind_verts, "SDefBindVerts (sparse)");
+}
+
 static bool surfacedeformBind(Object *ob,
                               SurfaceDeformModifierData *smd_orig,
                               SurfaceDeformModifierData *smd_eval,
@@ -1142,7 +1182,8 @@ static bool surfacedeformBind(Object *ob,
                               uint numverts,
                               uint tnumpoly,
                               uint tnumverts,
-                              Mesh *target)
+                              Mesh *target,
+                              Mesh *mesh)
 {
   BVHTreeFromMesh treeData = {NULL};
   const MVert *mvert = target->mvert;
@@ -1205,9 +1246,15 @@ static bool surfacedeformBind(Object *ob,
     return false;
   }
 
-  smd_orig->numverts = numverts;
+  smd_orig->num_mesh_verts = numverts;
   smd_orig->numpoly = tnumpoly;
 
+  int defgrp_index;
+  MDeformVert *dvert;
+  MOD_get_vgroup(ob, mesh, smd_orig->defgrp_name, &dvert, &defgrp_index);
+  const bool invert_vgroup = (smd_orig->flags & MOD_SDEF_INVERT_VGROUP) != 0;
+  const bool sparse_bind = (smd_orig->flags & MOD_SDEF_SPARSE_BIND) != 0;
+
   SDefBindCalcData data = {
       .treeData = &treeData,
       .vert_edges = vert_edges,
@@ -1221,6 +1268,10 @@ static bool surfacedeformBind(Object *ob,
       .vertexCos = vertexCos,
       .falloff = smd_orig->falloff,
       .success = MOD_SDEF_BIND_RESULT_SUCCESS,
+      .dvert = dvert,
+      .defgrp_index = defgrp_index,
+      .invert_vgroup = invert_vgroup,
+      .sparse_bind = sparse_bind,
   };
 
   if (data.targetCos == NULL) {
@@ -1242,6 +1293,13 @@ static bool surfacedeformBind(Object *ob,
 
   MEM_freeN(data.targetCos);
 
+  if (sparse_bind) {
+    compactSparseBinds(smd_orig);
+  }
+  else {
+    smd_orig->num_bind_verts = numverts;
+  }
+
   if (data.success == MOD_SDEF_BIND_RESULT_MEM_ERR) {
     BKE_modifier_set_error(ob, (ModifierData *)smd_eval, "Out of memory");
     freeData((ModifierData *)smd_orig);
@@ -1267,6 +1325,11 @@ static bool surfacedeformBind(Object *ob,
     BKE_modifier_set_error(ob, (ModifierData *)smd_eval, "Target contains invalid polygons");
     freeData((ModifierData *)smd_orig);
   }
+  else if (smd_orig->num_bind_verts == 0 || !smd_orig->verts) {
+    data.success = MOD_SDEF_BIND_RESULT_GENERIC_ERR;
+    BKE_modifier_set_error(ob, (ModifierData *)smd_eval, "No vertices were bound");
+    freeData((ModifierData *)smd_orig);
+  }
 
   freeAdjacencyMap(vert_edges, adj_array, edge_polys);
   free_bvhtree_from_mesh(&treeData);
@@ -1281,14 +1344,15 @@ static void deformVert(void *__restrict userdata,
   const SDefDeformData *const data = (SDefDeformData *)userdata;
   const SDefBind *sdbind = data->bind_verts[index].binds;
   const int num_binds = data->bind_verts[index].numbinds;
-  float *const vertexCos = data->vertexCos[index];
+  const unsigned int vertex_idx = data->bind_verts[index].vertex_idx;
+  float *const vertexCos = data->vertexCos[vertex_idx];
   float norm[3], temp[3], offset[3];
 
   /* Retrieve the value of the weight vertex group if specified. */
   float weight = 1.0f;
 
   if (data->dvert && data->defgrp_index != -1) {
-    weight = BKE_defvert_find_weight(&data->dvert[index], data->defgrp_index);
+    weight = BKE_defvert_find_weight(&data->dvert[vertex_idx], data->defgrp_index);
 
     if (data->invert_vgroup) {
       weight = 1.0f - weight;
@@ -1423,7 +1487,8 @@ static void surfacedeformModifier_do(ModifierData *md,
     /* Avoid converting edit-mesh data, binding is an exception. */
     BKE_mesh_wrapper_ensure_mdata(target);
 
-    if (!surfacedeformBind(ob, smd_orig, smd, vertexCos, numverts, tnumpoly, tnumverts, target)) {
+    if (!surfacedeformBind(
+            ob, smd_orig, smd, vertexCos, numverts, tnumpoly, tnumverts, target, mesh)) {
       smd->flags &= ~MOD_SDEF_BIND;
     }
     /* Early abort, this is binding 'call', no need to perform whole evaluation. */
@@ -1431,8 +1496,9 @@ static void surfacedeformModifier_do(ModifierData *md,
   }
 
   /* Poly count checks */
-  if (smd->numverts != numverts) {
-    BKE_modifier_set_error(ob, md, "Vertices changed from %u to %u", smd->numverts, numverts);
+  if (smd->num_mesh_verts != numverts) {
+    BKE_modifier_set_error(
+        ob, md, "Vertices changed from %u to %u", smd->num_mesh_verts, numverts);
     return;
   }
   if (smd->numpoly != tnumpoly) {
@@ -1468,8 +1534,8 @@ static void surfacedeformModifier_do(ModifierData *md,
 
     TaskParallelSettings settings;
     BLI_parallel_range_settings_defaults(&settings);
-    settings.use_threading = (numverts > 10000);
-    BLI_task_parallel_range(0, numverts, &data, deformVert, &settings);
+    settings.use_threading = (smd->num_bind_verts > 10000);
+    BLI_task_parallel_range(0, smd->num_bind_verts, &data, deformVert, &settings);
 
     MEM_freeN(data.targetCos);
   }
@@ -1554,6 +1620,11 @@ static void panel_draw(const bContext *UNUSED(C), Panel *panel)
 
   modifier_vgroup_ui(layout, ptr, &ob_ptr, "vertex_group", "invert_vertex_group", NULL);
 
+  col = uiLayoutColumn(layout, false);
+  uiLayoutSetEnabled(col, !is_bound);
+  uiLayoutSetActive(col, !is_bound && RNA_string_length(ptr, "vertex_group") != 0);
+  uiItemR(col, ptr, "use_sparse_bind", 0, NULL, ICON_NONE);
+
   uiItemS(layout);
 
   col = uiLayoutColumn(layout, false);
@@ -1576,10 +1647,10 @@ static void blendWrite(BlendWriter *writer, const ModifierData *md)
 {
   const SurfaceDeformModifierData *smd = (const SurfaceDeformModifierData *)md;
 
-  BLO_write_struct_array(writer, SDefVert, smd->numverts, smd->verts);
+  BLO_write_struct_array(writer, SDefVert, smd->num_bind_verts, smd->verts);
 
   if (smd->verts) {
-    for (int i = 0; i < smd->numverts; i++) {
+    for (int i = 0; i < smd->num_bind_verts; i++) {
       BLO_write_struct_array(writer, SDefBind, smd->verts[i].numbinds, smd->verts[i].binds);
 
       if (smd->verts[i].binds) {
@@ -1607,7 +1678,7 @@ static void blendRead(BlendDataReader *reader, ModifierData *md)
   BLO_read_data_address(reader, &smd->verts);
 
   if (smd->verts) {
-    for (int i = 0; i < smd->numverts; i++) {
+    for (int i = 0; i < smd->num_bind_verts; i++) {
       BLO_read_data_address(reader, &smd->verts[i].binds);
 
       if (smd->verts[i].binds) {