Speedup rigs with multiple objects deformed by bbones

Previously each of the objects which has armature modifier will
request deformation matricies from bbones. Thing is, all those
deformations are the same and do not depend on object which is
being modified. What's even worse is that this calculation is
not cheap.

This change makes it so bbones deformation is calculated once
and stored in the armature object. After this armature modifiers
simply use it.

With a rigs we've got here dependency graph evaluation time
goes down from 0.02 sec to 0.012 sec.

Possible further optimization is to make bbone deformation
calculated at the time when bone is calculated. This will avoid
an extra threaded loop over all bones.

6 files changed, 192 insertions, 57 deletions

diff --git a/source/blender/blenkernel/BKE_armature.h b/source/blender/blenkernel/BKE_armature.h
index 23a9afbda31..8ae29aee65c 100644
--- a/source/blender/blenkernel/BKE_armature.h
+++ b/source/blender/blenkernel/BKE_armature.h
@@ -253,6 +253,10 @@ void BKE_pose_splineik_evaluate(
         struct Object *ob,
         int rootchan_index);
 
+void BKE_pose_eval_done(
+        struct Depsgraph *depsgraph,
+        struct Object *object);
+
 void BKE_pose_eval_cleanup(
         struct Depsgraph *depsgraph,
         struct Scene *scene,
@@ -260,6 +264,8 @@ void BKE_pose_eval_cleanup(
 
 void BKE_pose_eval_proxy_init(struct Depsgraph *depsgraph,
                               struct Object *object);
+void BKE_pose_eval_proxy_done(struct Depsgraph *depsgraph,
+                              struct Object *object);
 void BKE_pose_eval_proxy_cleanup(struct Depsgraph *depsgraph,
                                  struct Object *object);
 
@@ -268,6 +274,18 @@ void BKE_pose_eval_proxy_copy_bone(
         struct Object *object,
         int pchan_index);
 
+/* BBOne deformation cache.
+ *
+ * The idea here is to pre-calculate deformation queternions, matricies and such
+ * used by armature_deform_verts().
+ */
+struct ObjectBBoneDeform;
+struct ObjectBBoneDeform * armature_cached_bbone_deformation_get(
+        struct Object *object);
+void armature_cached_bbone_deformation_free_data(struct Object *object);
+void armature_cached_bbone_deformation_free(struct Object *object);
+void armature_cached_bbone_deformation_update(struct Object *object);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenkernel/intern/armature.c b/source/blender/blenkernel/intern/armature.c
index ae28655bcfe..bd68caf1037 100644
--- a/source/blender/blenkernel/intern/armature.c
+++ b/source/blender/blenkernel/intern/armature.c
@@ -75,6 +75,8 @@
 
 #include "BIK_api.h"
 
+#include "atomic_ops.h"
+
 /* **************** Generic Functions, data level *************** */
 
 bArmature *BKE_armature_add(Main *bmain, const char *name)
@@ -813,6 +815,13 @@ typedef struct bPoseChanDeform {
 	DualQuat *b_bone_dual_quats;
 } bPoseChanDeform;
 
+/* Definition of cached object bbone deformations. */
+typedef struct ObjectBBoneDeform {
+	DualQuat *dualquats;
+	bPoseChanDeform *pdef_info_array;
+	int num_pchan;
+} ObjectBBoneDeform;
+
 static void pchan_b_bone_defmats(bPoseChannel *pchan, bPoseChanDeform *pdef_info, const bool use_quaternion)
 {
 	Bone *bone = pchan->bone;
@@ -1065,14 +1074,12 @@ void armature_deform_verts(
         float (*defMats)[3][3], int numVerts, int deformflag,
         float (*prevCos)[3], const char *defgrp_name, bGPDstroke *gps)
 {
-	bPoseChanDeform *pdef_info_array;
-	bPoseChanDeform *pdef_info = NULL;
+	const bPoseChanDeform *pdef_info = NULL;
 	bArmature *arm = armOb->data;
 	bPoseChannel *pchan, **defnrToPC = NULL;
 	int *defnrToPCIndex = NULL;
 	MDeformVert *dverts = NULL;
 	bDeformGroup *dg;
-	DualQuat *dualquats = NULL;
 	float obinv[4][4], premat[4][4], postmat[4][4];
 	const bool use_envelope   = (deformflag & ARM_DEF_ENVELOPE) != 0;
 	const bool use_quaternion = (deformflag & ARM_DEF_QUATERNION) != 0;
@@ -1081,7 +1088,6 @@ void armature_deform_verts(
 	int i, target_totvert = 0; /* safety for vertexgroup overflow */
 	bool use_dverts = false;
 	int armature_def_nr;
-	int totchan;
 
 	/* in editmode, or not an armature */
 	if (arm->edbo || (armOb->pose == NULL)) {
@@ -1098,21 +1104,20 @@ void armature_deform_verts(
 	mul_m4_m4m4(postmat, obinv, armOb->obmat);
 	invert_m4_m4(premat, postmat);
 
-	/* bone defmats are already in the channels, chan_mat */
-
-	/* initialize B_bone matrices and dual quaternions */
-	totchan = BLI_listbase_count(&armOb->pose->chanbase);
-
-	if (use_quaternion) {
-		dualquats = MEM_callocN(sizeof(DualQuat) * totchan, "dualquats");
+	/* Use pre-calculated bbone deformation.
+	 *
+	 * TODO(sergey): Make this code robust somehow when there are dependency
+	 * cycles involved. */
+	ObjectBBoneDeform * bbone_deform =
+	        armature_cached_bbone_deformation_get(armOb);
+	if (bbone_deform == NULL || bbone_deform->pdef_info_array == NULL) {
+		fprintf(stderr,
+		        "Armature does not have bbone cache %s, "
+		        "usually happens due to a dependency cycle.",
+		        armOb->id.name + 2);
+		return;
 	}
-
-	pdef_info_array = MEM_callocN(sizeof(bPoseChanDeform) * totchan, "bPoseChanDeform");
-
-	ArmatureBBoneDefmatsData data = {
-	    .pdef_info_array = pdef_info_array, .dualquats = dualquats, .use_quaternion = use_quaternion
-	};
-	BLI_task_parallel_listbase(&armOb->pose->chanbase, &data, armature_bbone_defmats_cb, totchan > 512);
+	const bPoseChanDeform *pdef_info_array = bbone_deform->pdef_info_array;
 
 	/* get the def_nr for the overall armature vertex group if present */
 	armature_def_nr = defgroup_name_index(target, defgrp_name);
@@ -1344,23 +1349,10 @@ void armature_deform_verts(
 		}
 	}
 
-	if (dualquats)
-		MEM_freeN(dualquats);
 	if (defnrToPC)
 		MEM_freeN(defnrToPC);
 	if (defnrToPCIndex)
 		MEM_freeN(defnrToPCIndex);
-
-	/* free B_bone matrices */
-	pdef_info = pdef_info_array;
-	for (pchan = armOb->pose->chanbase.first; pchan; pchan = pchan->next, pdef_info++) {
-		if (pdef_info->b_bone_mats)
-			MEM_freeN(pdef_info->b_bone_mats);
-		if (pdef_info->b_bone_dual_quats)
-			MEM_freeN(pdef_info->b_bone_dual_quats);
-	}
-
-	MEM_freeN(pdef_info_array);
 }
 
 /* ************ END Armature Deform ******************* */
@@ -2491,3 +2483,88 @@ bPoseChannel *BKE_armature_splineik_solver_find_root(
 	}
 	return rootchan;
 }
+
+/* ****************************** BBone cache  ****************************** */
+
+ObjectBBoneDeform * armature_cached_bbone_deformation_get(Object *object)
+{
+	return object->runtime.cached_bbone_deformation;
+}
+
+void armature_cached_bbone_deformation_free_data(Object *object)
+{
+	ObjectBBoneDeform *bbone_deform =
+	        armature_cached_bbone_deformation_get(object);
+	if (bbone_deform == NULL) {
+		return;
+	}
+	/* free B_bone matrices */
+	for (int i = 0; i < bbone_deform->num_pchan; i++) {
+		bPoseChanDeform *pdef_info = &bbone_deform->pdef_info_array[i];
+		if (pdef_info->b_bone_mats != NULL) {
+			MEM_freeN(pdef_info->b_bone_mats);
+		}
+		if (pdef_info->b_bone_dual_quats != NULL) {
+			MEM_freeN(pdef_info->b_bone_dual_quats);
+		}
+	}
+	/* Free arrays. */
+	MEM_SAFE_FREE(bbone_deform->pdef_info_array);
+	MEM_SAFE_FREE(bbone_deform->dualquats);
+	/* Tag that we've got no data, so we are safe for sequential calls to
+	 * data free. */
+	bbone_deform->num_pchan = 0;
+}
+
+void armature_cached_bbone_deformation_free(Object *object)
+{
+	ObjectBBoneDeform *bbone_deform =
+	        armature_cached_bbone_deformation_get(object);
+	if (bbone_deform == NULL) {
+		return;
+	}
+	armature_cached_bbone_deformation_free_data(object);
+	MEM_freeN(bbone_deform);
+	object->runtime.cached_bbone_deformation = NULL;
+}
+
+void armature_cached_bbone_deformation_update(Object *object)
+{
+	BLI_assert(object->type == OB_ARMATURE);
+	BLI_assert(object->pose != NULL);
+	bPose *pose = object->pose;
+	const int totchan = BLI_listbase_count(&pose->chanbase);
+	const bool use_quaternion = true;
+	/* Make sure cache exists. */
+	ObjectBBoneDeform *bbone_deform =
+	        armature_cached_bbone_deformation_get(object);
+	if (bbone_deform == NULL) {
+		bbone_deform = MEM_callocN(sizeof(*bbone_deform), "bbone deform cache");
+		object->runtime.cached_bbone_deformation = bbone_deform;
+	}
+	/* Make sure arrays are allocateds at the proper size. */
+	armature_cached_bbone_deformation_free_data(object);
+	DualQuat *dualquats = NULL;
+	if (use_quaternion) {
+		dualquats = MEM_calloc_arrayN(
+		        sizeof(DualQuat), totchan, "dualquats");
+	}
+	bPoseChanDeform *pdef_info_array = MEM_calloc_arrayN(
+	        sizeof(bPoseChanDeform), totchan, "bPoseChanDeform");
+	/* Calculate deofrmation matricies. */
+	ArmatureBBoneDefmatsData data = {
+		.pdef_info_array = pdef_info_array,
+		.dualquats = dualquats,
+		.use_quaternion = use_quaternion
+	};
+	BLI_task_parallel_listbase(&pose->chanbase,
+	                           &data,
+	                           armature_bbone_defmats_cb,
+	                           totchan > 512);
+	/* Store pointers. */
+	bbone_deform->dualquats = dualquats;
+	atomic_cas_ptr((void **)&bbone_deform->pdef_info_array,
+	               bbone_deform->pdef_info_array,
+	               pdef_info_array);
+	bbone_deform->num_pchan = totchan;
+}
diff --git a/source/blender/blenkernel/intern/armature_update.c b/source/blender/blenkernel/intern/armature_update.c
index c9e072caa6e..e882b64e8cc 100644
--- a/source/blender/blenkernel/intern/armature_update.c
+++ b/source/blender/blenkernel/intern/armature_update.c
@@ -585,21 +585,21 @@ BLI_INLINE bPoseChannel *pose_pchan_get_indexed(Object *ob, int pchan_index)
 
 void BKE_pose_eval_init(struct Depsgraph *depsgraph,
                         Scene *UNUSED(scene),
-                        Object *ob)
+                        Object *object)
 {
-	bPose *pose = ob->pose;
+	bPose *pose = object->pose;
 	BLI_assert(pose != NULL);
 
-	DEG_debug_print_eval(depsgraph, __func__, ob->id.name, ob);
+	DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
 
-	BLI_assert(ob->type == OB_ARMATURE);
+	BLI_assert(object->type == OB_ARMATURE);
 
 	/* We demand having proper pose. */
-	BLI_assert(ob->pose != NULL);
-	BLI_assert((ob->pose->flag & POSE_RECALC) == 0);
+	BLI_assert(object->pose != NULL);
+	BLI_assert((object->pose->flag & POSE_RECALC) == 0);
 
 	/* imat is needed for solvers. */
-	invert_m4_m4(ob->imat, ob->obmat);
+	invert_m4_m4(object->imat, object->obmat);
 
 	/* clear flags */
 	for (bPoseChannel *pchan = pose->chanbase.first; pchan != NULL; pchan = pchan->next) {
@@ -607,6 +607,7 @@ void BKE_pose_eval_init(struct Depsgraph *depsgraph,
 	}
 
 	pose_pchan_index_create(pose);
+	armature_cached_bbone_deformation_free_data(object);
 }
 
 void BKE_pose_eval_init_ik(struct Depsgraph *depsgraph,
@@ -746,41 +747,68 @@ void BKE_pose_splineik_evaluate(struct Depsgraph *depsgraph,
 	BKE_splineik_execute_tree(depsgraph, scene, ob, rootchan, ctime);
 }
 
-void BKE_pose_eval_cleanup(struct Depsgraph *depsgraph,
-                           Scene *scene,
-                           Object *ob)
+/* Common part for both original and proxy armatrues. */
+static void pose_eval_done_common(Object *object)
 {
-	bPose *pose = ob->pose;
+	bPose *pose = object->pose;
+	UNUSED_VARS_NDEBUG(pose);
+	BLI_assert(pose != NULL);
+	armature_cached_bbone_deformation_update(object);
+}
+static void pose_eval_cleanup_common(Object *object)
+{
+	bPose *pose = object->pose;
 	BLI_assert(pose != NULL);
-
-	float ctime = BKE_scene_frame_get(scene); /* not accurate... */
-	DEG_debug_print_eval(depsgraph, __func__, ob->id.name, ob);
-	BLI_assert(ob->type == OB_ARMATURE);
-
-	/* release the IK tree */
-	BIK_release_tree(scene, ob, ctime);
-
 	BLI_assert(pose->chan_array != NULL || BLI_listbase_is_empty(&pose->chanbase));
 	MEM_SAFE_FREE(pose->chan_array);
 }
 
+void BKE_pose_eval_done(struct Depsgraph *depsgraph, Object *object)
+{
+	bPose *pose = object->pose;
+	BLI_assert(pose != NULL);
+	UNUSED_VARS_NDEBUG(pose);
+	DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
+	BLI_assert(object->type == OB_ARMATURE);
+	pose_eval_done_common(object);
+}
+
+void BKE_pose_eval_cleanup(struct Depsgraph *depsgraph,
+                           Scene *scene,
+                           Object *object)
+{
+	bPose *pose = object->pose;
+	BLI_assert(pose != NULL);
+	UNUSED_VARS_NDEBUG(pose);
+	const float ctime = BKE_scene_frame_get(scene); /* not accurate... */
+	DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
+	BLI_assert(object->type == OB_ARMATURE);
+	/* Release the IK tree. */
+	BIK_release_tree(scene, object, ctime);
+	pose_eval_cleanup_common(object);
+}
+
 void BKE_pose_eval_proxy_init(struct Depsgraph *depsgraph, Object *object)
 {
 	BLI_assert(ID_IS_LINKED(object) && object->proxy_from != NULL);
 	DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
 
 	pose_pchan_index_create(object->pose);
+	armature_cached_bbone_deformation_free_data(object);
 }
 
-void BKE_pose_eval_proxy_cleanup(struct Depsgraph *depsgraph, Object *object)
+void BKE_pose_eval_proxy_done(struct Depsgraph *depsgraph, Object *object)
 {
 	BLI_assert(ID_IS_LINKED(object) && object->proxy_from != NULL);
 	DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
+	pose_eval_done_common(object);
+}
 
-	bPose *pose = object->pose;
-	BLI_assert(pose->chan_array != NULL);
-	MEM_freeN(pose->chan_array);
-	pose->chan_array = NULL;
+void BKE_pose_eval_proxy_cleanup(struct Depsgraph *depsgraph, Object *object)
+{
+	BLI_assert(ID_IS_LINKED(object) && object->proxy_from != NULL);
+	DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
+	pose_eval_cleanup_common(object);
 }
 
 void BKE_pose_eval_proxy_copy_bone(
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index 1a67822d260..0d3dfbeb382 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -458,6 +458,7 @@ void BKE_object_free_derived_caches(Object *ob)
 
 	object_update_from_subsurf_ccg(ob);
 	BKE_object_free_derived_mesh_caches(ob);
+	armature_cached_bbone_deformation_free(ob);
 
 	if (ob->runtime.mesh_eval != NULL) {
 		Mesh *mesh_eval = ob->runtime.mesh_eval;
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc
index 88e5ca9346c..eb2ed0e637d 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc
@@ -230,7 +230,9 @@ void DepsgraphNodeBuilder::build_rig(Object *object, bool is_object_visible)
 
 	op_node = add_operation_node(&object->id,
 	                             DEG_NODE_TYPE_EVAL_POSE,
-	                             NULL,
+	                             function_bind(BKE_pose_eval_done,
+	                                           _1,
+	                                           object_cow),
 	                             DEG_OPCODE_POSE_DONE);
 	op_node->set_as_exit();
 	/* Bones. */
@@ -379,7 +381,9 @@ void DepsgraphNodeBuilder::build_proxy_rig(Object *object)
 	                             DEG_OPCODE_POSE_CLEANUP);
 	op_node = add_operation_node(&object->id,
 	                             DEG_NODE_TYPE_EVAL_POSE,
-	                             NULL,
+	                             function_bind(BKE_pose_eval_proxy_done,
+	                                           _1,
+	                                           object_cow),
 	                             DEG_OPCODE_POSE_DONE);
 	op_node->set_as_exit();
 }
diff --git a/source/blender/makesdna/DNA_object_types.h b/source/blender/makesdna/DNA_object_types.h
index ffc798317ce..22b878ebac6 100644
--- a/source/blender/makesdna/DNA_object_types.h
+++ b/source/blender/makesdna/DNA_object_types.h
@@ -127,6 +127,11 @@ typedef struct ObjectDisplay {
 	int flag;
 } ObjectDisplay;
 
+/* Forward declaration for cache bbone deformation information.
+ *
+ * TODO(sergey): Consider moving it to more appropriate place. */
+struct ObjectBBoneDeform;
+
 /* Not saved in file! */
 typedef struct Object_Runtime {
 	/* Original mesh pointer, before object->data was changed to point
@@ -149,6 +154,8 @@ typedef struct Object_Runtime {
 
 	/* Runtime grease pencil drawing data */
 	struct GpencilBatchCache *gpencil_cache;
+
+	struct ObjectBBoneDeform *cached_bbone_deformation;
 } Object_Runtime;
 
 typedef struct Object {