Fix T59622: dependency problems with Spline IK.

The bug is caused by problems in the dependency graph. Unfortunately,
fixing is not just a matter of fixing the graph, because correct
dependencies would cause a cycle here and in other reasonable use
cases. The real fix thus requires refactoring Spline IK to require
curve data only in the actual evaluation phase, and not in POSE_INIT_IK.

In addition, this separates the normal bone evaluation loop from
Spline IK computations for two reasons:

- That still needs to be done even if spline IK can't evaluate
  due to missing curve data.

- It should reduce issues with induced shearing, as Spline IK now
  controls how parent-child relations are handled in the chain, and
  can take care to only carry over rotation and location.

2 files changed, 114 insertions, 111 deletions

diff --git a/source/blender/blenkernel/intern/armature_update.c b/source/blender/blenkernel/intern/armature_update.c
index 1e9febd4d8e..790f5cb2b31 100644
--- a/source/blender/blenkernel/intern/armature_update.c
+++ b/source/blender/blenkernel/intern/armature_update.c
@@ -56,10 +56,10 @@ typedef struct tSplineIK_Tree {
 
 	int type;                    /* type of IK that this serves (CONSTRAINT_TYPE_KINEMATIC or ..._SPLINEIK) */
 
-	bool free_points;            /* free the point positions array */
 	short chainlen;              /* number of bones in the chain */
+	float totlength;             /* total length of bones in the chain */
 
-	float *points;               /* parametric positions for the joints along the curve */
+	const float *points;         /* parametric positions for the joints along the curve */
 	bPoseChannel **chain;        /* chain of bones to affect using Spline IK (ordered from the tip) */
 
 	bPoseChannel *root;          /* bone that is the root node of the chain */
@@ -77,9 +77,8 @@ static void splineik_init_tree_from_pchan(Scene *UNUSED(scene), Object *UNUSED(o
 	bPoseChannel *pchanChain[255];
 	bConstraint *con = NULL;
 	bSplineIKConstraint *ikData = NULL;
-	float boneLengths[255], *jointPoints;
+	float boneLengths[255];
 	float totLength = 0.0f;
-	bool free_joints = 0;
 	int segcount = 0;
 
 	/* find the SplineIK constraint */
@@ -101,17 +100,6 @@ static void splineik_init_tree_from_pchan(Scene *UNUSED(scene), Object *UNUSED(o
 	if (con == NULL)
 		return;
 
-	/* make sure that the constraint targets are ok
-	 *     - this is a workaround for a depsgraph bug or dependency cycle...
-	 */
-	if (ikData->tar) {
-		CurveCache *cache = ikData->tar->runtime.curve_cache;
-
-		if (ELEM(NULL, cache, cache->path, cache->path->data)) {
-			return;
-		}
-	}
-
 	/* find the root bone and the chain of bones from the root to the tip
 	 * NOTE: this assumes that the bones are connected, but that may not be true... */
 	for (pchan = pchan_tip; pchan && (segcount < ikData->chainlen); pchan = pchan->parent, segcount++) {
@@ -168,41 +156,6 @@ static void splineik_init_tree_from_pchan(Scene *UNUSED(scene), Object *UNUSED(o
 	/* disallow negative values (happens with float precision) */
 	CLAMP_MIN(ikData->points[segcount], 0.0f);
 
-	/* apply corrections for sensitivity to scaling on a copy of the bind points,
-	 * since it's easier to determine the positions of all the joints beforehand this way
-	 */
-	if ((ikData->flag & CONSTRAINT_SPLINEIK_SCALE_LIMITED) && (totLength != 0.0f)) {
-		float splineLen, maxScale;
-		int i;
-
-		/* make a copy of the points array, that we'll store in the tree
-		 *     - although we could just multiply the points on the fly, this approach means that
-		 *       we can introduce per-segment stretchiness later if it is necessary
-		 */
-		jointPoints = MEM_dupallocN(ikData->points);
-		free_joints = 1;
-
-		/* get the current length of the curve */
-		/* NOTE: this is assumed to be correct even after the curve was resized */
-		splineLen = ikData->tar->runtime.curve_cache->path->totdist;
-
-		/* calculate the scale factor to multiply all the path values by so that the
-		 * bone chain retains its current length, such that
-		 *     maxScale * splineLen = totLength
-		 */
-		maxScale = totLength / splineLen;
-
-		/* apply scaling correction to all of the temporary points */
-		/* TODO: this is really not adequate enough on really short chains */
-		for (i = 0; i < segcount; i++)
-			jointPoints[i] *= maxScale;
-	}
-	else {
-		/* just use the existing points array */
-		jointPoints = ikData->points;
-		free_joints = 0;
-	}
-
 	/* make a new Spline-IK chain, and store it in the IK chains */
 	/* TODO: we should check if there is already an IK chain on this, since that would take precedence... */
 	{
@@ -211,14 +164,14 @@ static void splineik_init_tree_from_pchan(Scene *UNUSED(scene), Object *UNUSED(o
 		tree->type = CONSTRAINT_TYPE_SPLINEIK;
 
 		tree->chainlen = segcount;
+		tree->totlength = totLength;
 
 		/* copy over the array of links to bones in the chain (from tip to root) */
 		tree->chain = MEM_mallocN(sizeof(bPoseChannel *) * segcount, "SplineIK Chain");
 		memcpy(tree->chain, pchanChain, sizeof(bPoseChannel *) * segcount);
 
 		/* store reference to joint position array */
-		tree->points = jointPoints;
-		tree->free_points = free_joints;
+		tree->points = ikData->points;
 
 		/* store references to different parts of the chain */
 		tree->root = pchanRoot;
@@ -247,20 +200,69 @@ static void splineik_init_tree(Scene *scene, Object *ob, float UNUSED(ctime))
 
 /* ----------- */
 
-/* Evaluate spline IK for a given bone */
-static void splineik_evaluate_bone(
-        struct Depsgraph *depsgraph, tSplineIK_Tree *tree, Scene *scene, Object *ob, bPoseChannel *pchan,
-        int index, float ctime)
+typedef struct tSplineIk_EvalState {
+	float curve_position;        /* Current position along the curve. */
+	float curve_scale;           /* Global scale to apply to curve positions. */
+	float locrot_offset[4][4];   /* Bone rotation and location offset inherited from parent. */
+} tSplineIk_EvalState;
+
+/* Prepare data to evaluate spline IK. */
+static bool splineik_evaluate_init(tSplineIK_Tree *tree, tSplineIk_EvalState *state)
+{
+	bSplineIKConstraint *ikData = tree->ikData;
+
+	/* Make sure that the constraint targets are ok, to avoid crashes
+	 * in case of a depsgraph bug or dependency cycle.
+	 */
+	if (ikData->tar == NULL) {
+		return false;
+	}
+
+	CurveCache *cache = ikData->tar->runtime.curve_cache;
+
+	if (ELEM(NULL, cache, cache->path, cache->path->data)) {
+		return false;
+	}
+
+	/* Initialize the evaluation state. */
+	state->curve_position = 0.0f;
+	state->curve_scale = 1.0f;
+	unit_m4(state->locrot_offset);
+
+	/* Apply corrections for sensitivity to scaling. */
+	if ((ikData->flag & CONSTRAINT_SPLINEIK_SCALE_LIMITED) && (tree->totlength != 0.0f)) {
+		/* get the current length of the curve */
+		/* NOTE: this is assumed to be correct even after the curve was resized */
+		float splineLen = cache->path->totdist;
+
+		/* calculate the scale factor to multiply all the path values by so that the
+		 * bone chain retains its current length, such that
+		 *     maxScale * splineLen = totLength
+		 */
+		state->curve_scale = tree->totlength / splineLen;
+	}
+
+	return true;
+}
+
+/* Evaluate spline IK for a given bone. */
+static void splineik_evaluate_bone(tSplineIK_Tree *tree, Object *ob, bPoseChannel *pchan, int index, tSplineIk_EvalState *state)
 {
 	bSplineIKConstraint *ikData = tree->ikData;
-	float poseHead[3], poseTail[3], poseMat[4][4];
+	float origHead[3], origTail[3], poseHead[3], poseTail[3], poseMat[4][4];
 	float splineVec[3], scaleFac, radius = 1.0f;
 
-	/* firstly, calculate the bone matrix the standard way, since this is needed for roll control */
-	BKE_pose_where_is_bone(depsgraph, scene, ob, pchan, ctime, 1);
+	mul_v3_m4v3(poseHead, state->locrot_offset, pchan->pose_head);
+	mul_v3_m4v3(poseTail, state->locrot_offset, pchan->pose_tail);
+
+	copy_v3_v3(origHead, poseHead);
 
-	copy_v3_v3(poseHead, pchan->pose_head);
-	copy_v3_v3(poseTail, pchan->pose_tail);
+	/* first, adjust the point positions on the curve */
+	float curveLen = tree->points[index] - tree->points[index + 1];
+	float pointStart = state->curve_position;
+	float pointEnd = pointStart + curveLen * state->curve_scale;
+
+	state->curve_position = pointEnd;
 
 	/* step 1: determine the positions for the endpoints of the bone */
 	{
@@ -268,18 +270,18 @@ static void splineik_evaluate_bone(
 		float tailBlendFac = 1.0f;
 
 		/* determine if the bone should still be affected by SplineIK */
-		if (tree->points[index + 1] >= 1.0f) {
+		if (pointStart >= 1.0f) {
 			/* spline doesn't affect the bone anymore, so done... */
 			pchan->flag |= POSE_DONE;
 			return;
 		}
-		else if ((tree->points[index] >= 1.0f) && (tree->points[index + 1] < 1.0f)) {
+		else if ((pointEnd >= 1.0f) && (pointStart < 1.0f)) {
 			/* blending factor depends on the amount of the bone still left on the chain */
-			tailBlendFac = (1.0f - tree->points[index + 1]) / (tree->points[index] - tree->points[index + 1]);
+			tailBlendFac = (1.0f - pointStart) / (pointEnd - pointStart);
 		}
 
 		/* tail endpoint */
-		if (where_on_path(ikData->tar, tree->points[index], vec, dir, NULL, &rad, NULL)) {
+		if (where_on_path(ikData->tar, pointEnd, vec, dir, NULL, &rad, NULL)) {
 			/* apply curve's object-mode transforms to the position
 			 * unless the option to allow curve to be positioned elsewhere is activated (i.e. no root)
 			 */
@@ -295,7 +297,7 @@ static void splineik_evaluate_bone(
 		}
 
 		/* head endpoint */
-		if (where_on_path(ikData->tar, tree->points[index + 1], vec, dir, NULL, &rad, NULL)) {
+		if (where_on_path(ikData->tar, pointStart, vec, dir, NULL, &rad, NULL)) {
 			/* apply curve's object-mode transforms to the position
 			 * unless the option to allow curve to be positioned elsewhere is activated (i.e. no root)
 			 */
@@ -328,9 +330,7 @@ static void splineik_evaluate_bone(
 		/* compute the raw rotation matrix from the bone's current matrix by extracting only the
 		 * orientation-relevant axes, and normalizing them
 		 */
-		copy_v3_v3(rmat[0], pchan->pose_mat[0]);
-		copy_v3_v3(rmat[1], pchan->pose_mat[1]);
-		copy_v3_v3(rmat[2], pchan->pose_mat[2]);
+		mul_m3_m4m4(rmat, state->locrot_offset, pchan->pose_mat);
 		normalize_m3(rmat);
 
 		/* also, normalize the orientation imposed by the bone, now that we've extracted the scale factor */
@@ -361,6 +361,9 @@ static void splineik_evaluate_bone(
 		mul_m3_m3m3(tmat, dmat, rmat); /* m1, m3, m2 */
 		normalize_m3(tmat); /* attempt to reduce shearing, though I doubt this'll really help too much now... */
 		copy_m4_m3(poseMat, tmat);
+
+		/* apply rotation to the accumulated parent transform */
+		mul_m4_m3m4(state->locrot_offset, dmat, state->locrot_offset);
 	}
 
 	/* step 4: set the scaling factors for the axes */
@@ -470,19 +473,18 @@ static void splineik_evaluate_bone(
 		/* when the 'no-root' option is affected, the chain can retain
 		 * the shape but be moved elsewhere
 		 */
-		copy_v3_v3(poseHead, pchan->pose_head);
+		copy_v3_v3(poseHead, origHead);
 	}
 	else if (tree->con->enforce < 1.0f) {
 		/* when the influence is too low
 		 * - blend the positions for the 'root' bone
 		 * - stick to the parent for any other
 		 */
-		if (pchan->parent) {
-			copy_v3_v3(poseHead, pchan->pose_head);
+		if (index < tree->chainlen - 1) {
+			copy_v3_v3(poseHead, origHead);
 		}
 		else {
-			/* FIXME: this introduces popping artifacts when we reach 0.0 */
-			interp_v3_v3v3(poseHead, pchan->pose_head, poseHead, tree->con->enforce);
+			interp_v3_v3v3(poseHead, origHead, poseHead, tree->con->enforce);
 		}
 	}
 	copy_v3_v3(poseMat[3], poseHead);
@@ -491,9 +493,14 @@ static void splineik_evaluate_bone(
 	copy_m4_m4(pchan->pose_mat, poseMat);
 	copy_v3_v3(pchan->pose_head, poseHead);
 
+	mul_v3_mat3_m4v3(origTail, state->locrot_offset, pchan->pose_tail);
+
 	/* recalculate tail, as it's now outdated after the head gets adjusted above! */
 	BKE_pose_where_is_bone_tail(pchan);
 
+	/* update the offset in the accumulated parent transform */
+	sub_v3_v3v3(state->locrot_offset[3], pchan->pose_tail, origTail);
+
 	/* done! */
 	pchan->flag |= POSE_DONE;
 }
@@ -507,20 +514,28 @@ static void splineik_execute_tree(struct Depsgraph *depsgraph, Scene *scene, Obj
 	while ((tree = pchan_root->siktree.first) != NULL) {
 		int i;
 
-		/* walk over each bone in the chain, calculating the effects of spline IK
-		 *     - the chain is traversed in the opposite order to storage order (i.e. parent to children)
-		 *       so that dependencies are correct
-		 */
+		/* Firstly, calculate the bone matrix the standard way, since this is needed for roll control. */
 		for (i = tree->chainlen - 1; i >= 0; i--) {
-			bPoseChannel *pchan = tree->chain[i];
-			splineik_evaluate_bone(depsgraph, tree, scene, ob, pchan, i, ctime);
+			BKE_pose_where_is_bone(depsgraph, scene, ob, tree->chain[i], ctime, 1);
+		}
+
+		/* After that, evaluate the actual Spline IK, unless there are missing dependencies. */
+		tSplineIk_EvalState state;
+
+		if (splineik_evaluate_init(tree, &state)) {
+			/* Walk over each bone in the chain, calculating the effects of spline IK
+			 *     - the chain is traversed in the opposite order to storage order (i.e. parent to children)
+			 *       so that dependencies are correct
+			 */
+			for (i = tree->chainlen - 1; i >= 0; i--) {
+				bPoseChannel *pchan = tree->chain[i];
+				splineik_evaluate_bone(tree, ob, pchan, i, &state);
+			}
 		}
 
 		/* free the tree info specific to SplineIK trees now */
 		if (tree->chain)
 			MEM_freeN(tree->chain);
-		if (tree->free_points)
-			MEM_freeN(tree->points);
 
 		/* free this tree */
 		BLI_freelinkN(&pchan_root->siktree, tree);
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations_rig.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations_rig.cc
index ed1ae5631ad..9fd4a8dc802 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_relations_rig.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_relations_rig.cc
@@ -261,8 +261,10 @@ void DepsgraphRelationBuilder::build_splineik_pose(Object *object,
 	             RELATION_FLAG_GODMODE);
 	/* Attach path dependency to solver. */
 	if (data->tar != NULL) {
-		ComponentKey target_key(&data->tar->id, NodeType::GEOMETRY);
-		add_relation(target_key, init_ik_key, "Curve.Path -> Spline IK");
+		ComponentKey target_geometry_key(&data->tar->id, NodeType::GEOMETRY);
+		add_relation(target_geometry_key, solver_key, "Curve.Path -> Spline IK");
+		ComponentKey target_transform_key(&data->tar->id, NodeType::TRANSFORM);
+		add_relation(target_transform_key, solver_key, "Curve.Transform -> Spline IK");
 		add_special_eval_flag(&data->tar->id, DAG_EVAL_NEED_CURVE_PATH);
 	}
 	pchan->flag |= POSE_DONE;
@@ -271,41 +273,27 @@ void DepsgraphRelationBuilder::build_splineik_pose(Object *object,
 	add_relation(solver_key, final_transforms_key, "Spline IK Result");
 	root_map->add_bone(pchan->name, rootchan->name);
 	/* Walk to the chain's root/ */
-	int segcount = 0;
+	int segcount = 1;
 	for (bPoseChannel *parchan = pchan->parent;
-	     parchan != NULL;
-	     parchan = parchan->parent)
+	     parchan != NULL && segcount < data->chainlen;
+	     parchan = parchan->parent, segcount++)
 	{
 		/* Make Spline IK solver dependent on this bone's result, since it can
 		 * only run after the standard results of the bone are know. Validate
 		 * links step on the bone will ensure that users of this bone only grab
 		 * the result with IK solver results. */
-		if (parchan != pchan) {
-			OperationKey parent_key(&object->id,
-			                        NodeType::BONE,
-			                        parchan->name,
-			                        OperationCode::BONE_READY);
-			add_relation(parent_key, solver_key, "Spline IK Solver Update");
-			OperationKey bone_done_key(&object->id,
-			                           NodeType::BONE,
-			                           parchan->name,
-			                           OperationCode::BONE_DONE);
-			add_relation(solver_key, bone_done_key, "IK Chain Result");
-		}
+		OperationKey parent_key(&object->id,
+								NodeType::BONE,
+								parchan->name,
+								OperationCode::BONE_READY);
+		add_relation(parent_key, solver_key, "Spline IK Solver Update");
+		OperationKey bone_done_key(&object->id,
+								   NodeType::BONE,
+								   parchan->name,
+								   OperationCode::BONE_DONE);
+		add_relation(solver_key, bone_done_key, "Spline IK Solver Result");
 		parchan->flag |= POSE_DONE;
-		OperationKey final_transforms_key(&object->id,
-		                                  NodeType::BONE,
-		                                  parchan->name,
-		                                  OperationCode::BONE_DONE);
-		add_relation(
-		        solver_key, final_transforms_key, "Spline IK Solver Result");
 		root_map->add_bone(parchan->name, rootchan->name);
-		/* TODO(sergey): This is an arbitrary value, which was just following
-		 * old code convention. */
-		segcount++;
-		if ((segcount == data->chainlen) || (segcount > 255)) {
-			break;
-		}
 	}
 	OperationKey pose_done_key(
 	        &object->id, NodeType::EVAL_POSE, OperationCode::POSE_DONE);