`A4T2` Skeleton Kinematics

A Skeleton (declared in src/scene/skeleton.h, defined in src/scene/skeleton.cpp) is what we use to drive our animation. You can think of them like the set of bones we have in our own bodies and joints that connect these bones. For convenience, we have merged the bones and joints into the Bone class which holds the orientation of the bone relative to its parent as Euler angles (Bone::pose), and an extent that specifies where its child bones start. Each Skinned_Mesh has an associated Skeleton class which holds a rooted tree of Boness, where each Bone can have an arbitrary number of children.

When discussing skeletal animation we have a whole family of different transformations and spaces to consider:

World space is the space of the scene.
Local space is the coordinate system local to the Skinned_Mesh. It is shared by the Skinned_Mesh::mesh and the Skinned_Mesh::skeleton. The transformation, $L$ , between local space and world space is determined by the scene graph and can be retrieved from Instance::Skinned_Mesh::transform->local_to_world() (which you wrote way back in A1!).
Bone space has its origin at the base point of the bone and its axes rotated by the bone (and its parents) rotations. There are two different bone spaces we will talk about:
- Bind Space is the bone space in the bind pose (the pose where all joints are not rotated). The transformations, $B_j$ , from bone space to local space for all bones $j$ is computed by Skeleton::bind_pose() (which you will implement).
- Pose Space is the bone space in the current pose (the pose where each bone and its children are rotated by Bone::pose around Bone::compute_rotation_axes). The transformations, $P_j$ , from pose space to local space for all bones $j$ are computed by Skeleton::current_pose() (which you will also implement).

NOTE: I mention world space above because it is one of the coordinate systems in Scotty3D. But for all of the implementation details of this assignment, you'll be working in local space and/or the bone spaces. Indeed, it is not possible from within Skeleton to determine $L$ , since Skeletons don't know what instance they are being accessed through.

`A4T2a` Forward Kinematics

Implement:

Skeleton::bind_pose, which returns a vector whose $i\textrm{th}$ entry is $B_j \equiv \hat{X}_{\emptyset \gets i}$ .
Skeleton::current_pose, which returns a vector whose $i\textrm{th}$ entry is $P_i \equiv X_{\emptyset \gets i}$ .

In the first half of this task, you will implement Skeleton::bind_pose and Skeleton::current_pose, which compute all the bind-to-local and pose-to-local transformations $B_j$ and $P_j$ , respectively. It makes sense to compute these transformations in bulk because they are defined recursively in terms of a bone-to-parent transformation.

The transform between every bone's local space its parent is a rotation around a local $x$ , $y$ , and $z$ rotation axis (in that order) followed by a translation by the parent's extent.

In other words, given bone $b$ with rotation axis directions $x_b$ , $y_b$ , and $z_b$ ; local rotation amounts $rx_b$ , $ry_b$ , and $rz_b$ ; and parent bone $p$ with extent $e_p$ , the transform that takes points in the local space of $b$ to the local space of $p$ is the matrix:

$X_{p \gets b} \equiv T_{p_e} R_{rz_b @ z_b} R_{ry_b @ y_b} R_{rx_b @ x_b}$

Where $T_{p_e}$ is a translation by $p_e$ and $R_{ra @ a}$ rotates by angle $ra$ around axis $a$ .

Bones without a parent are translated by the skeleton's base point, $r$ , and current base offset, $o$ : $<span class="arithmatex"><span class="MathJax_Preview">X_{\emptyset \gets b} \equiv T_{r+o}</span><script type="math/tex">X_{\emptyset \gets b} \equiv T_{r+o}$

The overall transform from each bone to local space can be computed recursively: $<span class="arithmatex"><span class="MathJax_Preview">X_{\emptyset \gets b} \equiv X_{\emptyset \gets p} X_{p \gets b}</span><script type="math/tex">X_{\emptyset \gets b} \equiv X_{\emptyset \gets p} X_{p \gets b}$

In the bind pose the bones are not posed or offset, so we have:

for bone $b$ with parent $p$ , $\hat{X}\_{p \gets b} \equiv T\_{p\_e}$

for bone $b$ without parent, $\hat{X}\_{\emptyset \gets b} \equiv T\_{r}$

and, recursively, $\hat{X}\_{\emptyset \gets b} \equiv \hat{X}\_{\emptyset \gets p} \hat{X}\_{p \gets b}$

Implementation notes: - The list of bones in the skeleton is guaranteed to be sorted such that bones' parents appear first, so your code should be able to work in a single pass through the bones array. - The functions Mat4::angle_axis and Mat4::translate will be helpful.

Aside: Local Axes

Why do we bother specifying $x_b$ , $y_b$ , $z_b$ ? Having a good choice of local axis is important when rigging characters for effective posing. If a joint has one primary axis of rotation, you'd prefer to have that axis aligned with (say) $rx_b$ so you need only adjust one variable when animating. This is especially important with mechanical assemblies, where you may well want a joint to represent a 1-DOF hinge, which is hard if the hinge is not parallel to some local axis of rotation!

The local rotation axes for a bone in Scotty3D are defined as follows (already implemented for you in the Bone::compute_rotation_axes function).

The $y_b$ axis is aligned with the bone's extent: $<span class="arithmatex"><span class="MathJax_Preview">y_b \equiv \mathrm{normalize}(e_b)</span><script type="math/tex">y_b \equiv \mathrm{normalize}(e_b)$ (In case the bone's extent is zero, $y_b$ is set to $(0,1,0)$ .)

To define $x_b$ we start with $\hat{x}$ , the axis perpendicular to $y_b$ and aligned with the skeleton's $x$ axis: $<span class="arithmatex"><span class="MathJax_Preview">\hat{x} \equiv \mathrm{normalize}((1,0,0) - ((1,0,0) \cdot y_b) y_b)</span><script type="math/tex">\hat{x} \equiv \mathrm{normalize}((1,0,0) - ((1,0,0) \cdot y_b) y_b)$ (In case $y_b$ is parallel to the $x$ axis, $\hat{x}$ is set to $(0,0,1)$ .)

The $x_b$ axis is $\hat{x}$ rotated by $\theta_b \equiv$ bone.roll around $y_b$ : $<span class="arithmatex"><span class="MathJax_Preview">x_b \equiv \cos(\theta_b) \hat{x} - \sin(\theta_b) (\hat{x} \times y_b)</span><script type="math/tex">x_b \equiv \cos(\theta_b) \hat{x} - \sin(\theta_b) (\hat{x} \times y_b)$

And, finally, the $z_b$ axis is set perpendicular to $x_b$ and $y_b$ to form a right-handed coordinate system: $<span class="arithmatex"><span class="MathJax_Preview">z_b \equiv x_b \times y_b</span><script type="math/tex">z_b \equiv x_b \times y_b$

A picture of what's going on

Note: These diagrams are in 2D for visual clarity, but we will work with a 3D kinematic skeleton.

Just like a Scene::Transform, the pose (and extent) of a Bone transform all of its children. In the diagram below, $c_0$ is the parent of $c_1$ and $c_1$ is the parent of $c_2$ . When a translation of $x_0$ and rotation of $\theta_0$ is applied to $c_0$ , all of the descendants are affected by this transformation as well. Then, $c_1$ is rotated by $\theta_1$ which affects itself and $c_2$ . Finally, when rotation of $\theta_2$ is applied to $c_2$ , it only affects itself because it has no children.

Once you have implemented these basic kinematics, you should be able to define skeletons, set their positions at a collection of keyframes, and watch the skeleton smoothly interpolate the motion (see the user guide for an explanation of the interface and some demo videos).

Note that the skeleton does not yet influence the geometry of meshes in the scene -- that will come in Task 3!

`A4T2b` Inverse Kinematics

Implement:

Skeleton::gradient_in_current_pose, which returns $\nabla f$ .
Skeleton::solve_ik, takes downhill steps in bone pose space to minimize $f$ .

Now that we have a logical way to move joints around, we can implement Inverse Kinematics (IK), which will move the joints around in order to reach a target point. There are a few different ways we can do this, but for this assignment we'll implement an iterative method called gradient descent in order to find the minimum of a function. For a function $f : \mathbb{R}^n \to \mathbb{R}$ , we'll have the update scheme:

$q \gets q - \tau \nabla f$

Where $\tau$ is a small timestep and $q$ holds all the Bone::pose qordinates. Specifically, we'll be using gradient descent to find the minimum of a cost function which measures the total squared distance between a set of IK handles positions $h$ and their associated bones $b$ :

$f(q) = \sum_{(h,i)} \frac{1}{2}|p_i(q) - h|^2$

Where $p\_i(q) = I_{3\times 4} X\_{\emptyset \gets i } [ e_i ~ 1 ]^T$ is the end position of bone $i$ . (Here $I_{3\times 4}$ is a 3-row, 4-column matrix with ones on the diagonal to strip the homogenous coordinate, leaving just the position component. This is okay to do as long as $X$ is made up of well-behaved translations and rotations that don't (say) scale the homogenous coordinate.)

Implementation Notes:

If your updates become unstable, use a smaller $\tau$ (timestep).
For even faster and better results, you can also implement a variable timestep instead of a fixed one. (One strategy: do a binary search to find a step which produces the large decrease in $f$ along $-\nabla f$ .)
Gradient descent should never affect Skeleton::base_offset.
Remember what coordinate frame you're in. If you calculate the gradients in the wrong coordinate frame or use the axis of rotation in the wrong coordinate frame your answers will come out very wrong!
Gradient descent is hard to get perfectly right because (especially with adaptive stepping!) it is a method that really wants to work. Sometimes it's hard to distinguish an inefficient implementation from an incorrect one.

Computing $\nabla f$

The gradient of $f$ (i.e., $\nabla f$ ) is the vector consisting of the partial derivatives of $f$ with respect to every element of $q$ . So let's look at one example: let's take the partial derivative with respect to $ry_b$ -- the rotation around the local $y_b$ axis of bone $b$ .

First, we expand the definition of $f$ : $$\frac{\partial}{\partial ry_b} f = \sum_{(h,i)} \frac{\partial}{\partial ry_b} \frac{1}{2}|p_i(\mathbf{\theta}) - h|^2 $$

In other words, we can compute the partial derivatives for each IK handle individually and sum them. Any IK handle where $b$ isn't in the kinematic chain will contribute nothing to the partial derivative, so let's look at a handle whose bone is a descendant of $b$ , and apply the chain rule:

$\frac{\partial}{\partial ry_b} \frac{1}{2}|p_i(q) - h|^2 = (p_i(q) - h) \cdot \frac{\partial}{\partial ry_b} p_i(q)$

Then expand the definition of $p_i$ : $$= (p_i(q) - h) \cdot \frac{\partial}{\partial ry_b} X_{\emptyset \gets i} [ e_i ~ 1 ]^T $$ $$= (p_i(q) - h) \cdot \frac{\partial}{\partial ry_b} X_{\emptyset \gets \ldots \gets c} X_{c \gets b} X_{b \gets \ldots \gets i} [ e_i ~ 1 ]^T $$

$= (p_i(q) - h) \cdot ( \underbrace{X_{\emptyset \gets \ldots \gets c} T_{c_e} R_{rz_b @ z_b}}\_{\textrm{linear xform}} \underbrace{\frac{\partial}{\partial ry_b} R_{ry_b @ y_b}}\_{\textrm{rotation}} \underbrace{R\_{rx\_b @ x\_b} X\_{b \gets \ldots \gets i} [ e\_i ~ 1 ]^T}\_{\textrm{some point}} )$

In other words, your code needs only to find partial derivative of a rotation relative to its angle, and project this partial derivative to skeleton-local space.

Here's a useful bit of geometric reasoning: if you transform the axis of rotation and the base point of the bone into skeleton local space, then you can use the fact that the derivative (w.r.t. $\theta$ ) of the rotation by $\theta$ around axis $x$ and center $r$ of point $p$ is a vector perpendicular $x$ with length $|r-p|$ :

$\frac{\partial}{\partial \theta} R_{\theta @ x} (p - r) + r = x \times (p - r)$

For a more in-depth derivation of the process of computing this derivative (and a look into other inverse kinematics algorithms), please check out this presentation. (Pages 45-56 in particular)

Using your IK!

Once you have IK implemented, you should be able to create a series of joints, and get a particular joint to move to the desired final position you have selected.

Please refer to the User Guide for more examples

Table of Content

A4T2 Skeleton Kinematics

A4T2a Forward Kinematics