A reference implementation of the virtual mannequin, showing a model in one sculpted pose.

In this project, you will implement a skinning system -- a way to animate a 3D character by manipulating bones embedded inside the character. To deform the character using skinning, you will implement a basic mouse-based bone selection and rotation interface.

Starter Code

Building and Running the Starter Code

mkdir build
cd build
cmake ..
make

Submission Instructions

tar --exclude obj --exclude build --exclude ".*" -czf submission.tgz foldername

• Your name;
• An explanation of any required features that you know are not working completely correctly, but would like to have considered for partial credit;
• Anything the spec below asks you to include.

In particular,

• Do not submit a 7zip of a Visual Studio .soln file;
• Do not include any absolute paths in your Makefiles that point to your home folder;
• If you use any external libraries (which must be approved in advance by the instructor) that are not installed by default on the GDC computers, you must include the library source files with your submission, and include building of the library in your build process.

Tip: After uploading your files to Canvas, it is not a bad idea to download them onto a different computer and check that it still compiles and runs, in case you accidentally leave out some important files from the .tgz. It is also wise to try to upload to Canvas well ahead of the final deadline: again, there will be no exceptions to the lateness policy, not even for technical difficulties.

Grading

Required Features (150 points)

Parsing the Joints and Weights (30 points)

We have provided code for parsing and rendering the model mesh. Your first task will be to build data structures for representing the skeleton, bones, joints, and blending weights, and to populate these data structures from the provided PMD file.

The skeleton is represented using a forest of bones which connect pairs of joints. The PMD file contains only information about the joints, from which the bones and skeleton can be reconstructed. Each joint has

• an integer ID identifying the joint;

• the ID of the parent joint. If this ID is equal to -1, then the joint has no parent - it is a root joint. Otherwise, there exists a bone extending from the parent joint to the current joint.

• an offset vector which gives the joint's initial ("rest") position in world coordinates in terms of its parent's initial position. If the joint is a root joint, the offset vector simply specifies its position with respect to the origin in world coordinates.

You will want to convert this endpoint-based data into a bone data structure. Each bone has a coordinate system whose origin is its first endpoint, and whose basis vectors are

• the tangent direction \(\hat{t}\), which points from the bone's first endpoint to its second endpoint;
• the normal direction \(\hat{n}\), an arbitrary unit vector perpendicular to \(\hat{t}\). Given \(\hat{t}\), you can compute such a vector with the following algorithm. Set \(v=\hat{t}\), then set the entry of v with smallest magnitude to 1, and the other two entries to zero. Finally compute \(\hat{n} = \frac{\hat{t} \times v}{\|\hat{t} \times v\|}\).
• the binormal direction \(\hat{b} = \hat{t}\times \hat{n}\).

1. the translation T_i, in the coordinate system of the parent's bone, which maps the parent's origin (first endpoint) to the bone's origin. For all bones in this assignment, T_i should translate only the first coordinate (corresponding to translating along the parent's \(\hat{t}\) direction). (Translations of the second or third coordinate would correspond to dislocated bones that are not attached to the parent bone.)
2. the rotation R_i which maps the parent coordinate axes to the bone's coordinate axes.

For example, suppose bone 7 is connected to bone 4, which is connected to bone 1, which is connected to bone 0, which has no parent. If the coordinate systems are set up correctly, the origin of bone 7 should be at \[T_0R_0T_1R_1T_4R_4T_7\left[\begin{array}{c}0\\0\\0\\1\end{array}\right]\], the second endpoint at \[T_0R_0T_1R_1T_4R_4T_7R_7\left[\begin{array}{c}0\\0\\L\\1\end{array}\right]\] where L is bone 7's length, and the \(\hat{t}, \hat{n}\), and \(\hat{b}\) axis should be given by \[R_0R_1R_4R_7.\]

Create a data structure which stores, for each bone, its source and destination joints, its length, and its T and R matrices. Finally, write code to visualize the bones as line segments.

We have implemented a translucency mode when rendering the mesh to make it easier to work with the skeleton. Hit t to toggle translucency mode. The bones should be visible within the mesh whenever translucency mode is turned on (obviously the bones will be mostly hidden when the mesh is opaque; this is fine.)

Notes: (ignore these if they are more confusing than helpful)

Skeleton Construction:

Recursive tree-like construction takes much of the pain of this away.

Joints can have child joints and can be viewed much like nodes. Bones have a (from, to) tuple which specifies the joint they come from and the joint they go to.

Joints can keep other things, such as their reference orientation (this is a matrix), which is useful when implementing the skinning part.

Pose Updates:

You can keep a boolean around to tell whether the pose has been changed or not.

Pose updates are not too hard if this is done recursively. You should implement a function that updates a joint and recursively updates all the children.

These updates will typically just be rotations applied to the joint. Along with a rotation R, you will have a translation T htat translates the origin to the current joint position. The transformation you want is <(T_inv * R * T\). This transformation, when applied recursively, will rotate the initial joint, rotating it by R in its own coordinate system, and then rotate all of its children relative to it.

Constructing the Bone Orientation Matrix:

You will have the direction of the bone and you will need to produce a matrix that gives them an orientation for the bone. This is similar to a camera LookAt() routine, but there is no eye position, and you only get to start with one vector.

You just need to generate a vector that is *not* parallel to the bone direction. One way to do this is to find the smallest component of the bone direction and generate \(e_j\) where j is the index of the smallest component. Then take two cross products to get the other two vectors.

Bone Picking (50 points)

• (5 points) Each time the user moves the mouse, convert the position of the mouse cursor in screen coordinates to a ray in world coordinates, whose origin p is at the eye's position, and whose direction v is such that the ray from p in the v direction pierces the near plane at the pixel containing the mouse cursor.

• (35 points) The bones, when rendered as line segments, are very thin and hard to click on; to make the user interface easier to use, we will thicken the bones into cylinders of radius kCylinderRadius for the purposes of detecting which bone the user intends to click on.

  The details of ray-cylinder intersection are up to you. One way to proceed is to first find the closest point \(c_0\) on the ray \(p + tv\) to the infinite line passing through the cylinder's axis. If the distance between \(c_0\) and the infinite line is greater than kCylinderRadius, the ray misses the cylinder. Also, if the value of t corresponding to \(c_0\) is negative, the cylinder is behind the eye and the ray misses the cylinder. Otherwise, project \(c_0\) onto the cylinder's axis, and check whether the projected point is between the two cylinder endcaps. If so, the ray hits the cylinder; otherwise, the ray misses (there is a corner case where the ray hits one endcap, pierces the entire length of the cylinder, and leaves through the other endcap, which is declared a miss by this procedure. But this corner case is rare enough that you can ignore it.)

  If the ray hits one or more cylinders, the first such cylinder hit becomes the highlighted cylinder. Otherwise, no cylinders are highlighted.

• (10 points) Visualize highlighted bones by drawing a wireframe prism approximating a cylinder of radius kCylinderRadius (and same length as the bone) around the highlighted bone. (I recommend precomputing the vertices and faces of a single prism, scaling it to match the length of the bone, and transforming it to the correct position and orientation using the R and T matrices.) Also visualize the \(\hat{n}\) and \(\hat{b}\) directions for the highlighted bone, using short red and blue line segments anchored at the bone's origin point. (Obviously, the \(\hat{t}\) direction points down the length of the bone, so there is no need to visualize it separately.)

There are two parts to bone picking:

1. Ray generation. Implement a ScreenToWorld function that generates a world space point given screen space (x, y).

   There are several ways to do this:

   1. Use the camera matrix:
      1. calculate the width and height (w, h) of the image plane in world coordinates (you need to know the field of view)
      2. calculate ndc.x, ndc.y
      3. use (ndc.x, ndc.y), (w, h), look, up, tangent to get the world space coordinates
   2. Use the projection matrix:
      1. unproject (x, y, 0) to get the world space coordinates
      2. Once you have this, subtract the eye position to get a world space ray.
   3. Another method is:
      1. let q be unproject (x, y, 0),
      2. let p be unproject (x, y, 1),
      3. take the ray through the two points p and q.

2. Cylinder intersection.

   Implement a cylinder/ray intersection routine where the cylinder points straight up and is centered at the origin (or lying on its side), has radius R, and height H. Transform the ray into the cylinder's coordinates. Use the bone orientation matrix to do this. The orientation matrix needs to be *just* the orientation (no translation).

   Turn this problem into a 2D problem. Project the line onto the (x, z) plane and intersect a line with a circle of radius R. If the ray misses the circle, reject the ray. Else check the intersection times \(t_0\) and \(t_1\) and see if they are good. Compute the intersection points and take the closest good one. A point is good if it has a y-value between 0 and H. This algorithm does not handle intersection at the caps.

Generate a \(n \times n\) two-dimensional grip of lines. Use a model transformation which is the bone transformation with a scale along the y-axis applied to stretch the cylinder out, and a scale in the x-z plane to widen the cylinder. The bone transformation won't contain a scale, since it has to be purely a rotation.

The vertex shader can wrap the line mesh around (0,0) using \(\cos(\theta), \sin(\theta)\).

Bone Drawing:

You are just drawing a bunch of lines. In fact, all the shade does is draw a single line. The line is transformed by the bone transform and a scale along the y-axis. You should instance the line and the transformation matrices you send to the shader.

Bone Manipulation (25 points)

• (5 points) Modify your bone data structure to also track \(S_i\) for each bone. Modify your rendering and bone-picking code to use the deformed bone postiion (given by the \(T_i\) and \(S_i\)) rather than starting bone position (given by the \(T_i\) and \(R_i\)).

• (15 points) Left-clicking and dragging the mouse should rotate the bone relative to the camera coordinate system. That is, convert the drag direction into a vector in world coordinates, take its cross product with the look direction, and rotate all basis vectors \(S_i\) of the bone about this axis by rotation_speed radians. (This calculation should remind you of the FPS camera controls).

• (5 points) Pressing the left and right arrow keys in bone-movement mode should roll the highlighted bone: spin the bone about its tangent axis \(\hat{t}\) by roll_speed radians.

Linear Blend Skinning (35 points)

The PMD file contains weights which specify how much influence each joint has on each vertex of the model mesh. You will first need to convert these into a (# bones) \(\times\) (# vertices) matrix of per-bone blending weights, which tell you how much influence each bone has on each vertex of the mesh.

• (10 points) Compute and store weights \(w_{ij}\), encoding the influence of bone i on vertex j, in a data structure. We have provided code for reading joint weights from the PMD file. To convert joint weights to bone weights, assign a weight for joint i to all bones which have that joint as their source (parent) joint. This means that each joint weight might turn into multiple different bone weights; similarly, joints at the leaves of the skeleton forest (at the fingertips, for instance) will have no joint weights.

• (10 points) Every frame, for each bone, compute the overall transformation \(U_i\) that maps from the bone's undeformed coordinate system to world coordinates, and the overall transformation \(D_i\) that maps from the bone's deformed coordinates to world coordinates.

• (15 points) Implement linear-blend skinning: every frame, transform each undeformed vertex \(v_j\) of the ogre using the transformation \[\tilde{v}_j = \sum_{\mathrm{bones\ } i} w_{ij} D_iU_i^{-1}v_j\] to get the current, deformed position of the vertex \(\tilde{v}_j\).

Linear Blend Skinning: This is easier than it seems.

1. Compute blending matrices:

   For each bone you have a reference pose. Invert that pose. In fact, invert it once and save it for later, it never changes.

   You have a current animated pose as well. So, for each bone j you will produce a blending matrix: \(B_j\) = current_bone_transformation * inv_reference_pose.

   Compute all the blending matrices first.

2. Transform each vertex:

   The transformation \(T_i\) for a vertex i is a sum of the \(B_j\) weighted by the weight \(w_{ij}\) where \(w_{ij}\) corresponds to bone j and vertex i.

   Transform vertex i by T.

3. Render!

Miscellaneous (10 points)

Extra Credit (up to 50 points)

• some of the example models exhibit z-fighting, due to loss of precision in the depth buffer (see comments in code near kNear in config.h for details). This loss of precision is due to the way that the projection matrix maps depth into normalized device coordinates non-linearly. Fix the problem.

• instead of performing the matrix blending on the CPU, do everything on the GPU using shaders.

• linear-blend skinning is very popular thanks to its simplicity, but has well-known "pinching" and volume-loss artifacts. Implement dual-quaternion skinning, the current state-of-the-art skinning algo- rithm;

• find a cool mesh online and rig it with your own bones file;

• implement pose keyframing: the user specifies a few deformed poses for the ogre, and hits a key; the program then animates the ogre by interpolating between the keyframed poses;

• Your code must obey the above spec and match the reference solution. In other words, you can add new features for extra credit, but should not modify the way that existing features function. You will be deducted points if your extra credit work causes your program to violate the spec! This includes the functionality of the T key: if you want to extend the number or types of texture supported, add a new key that enables the ``extra'' textures (and document it in your README).

• Include a brief explanation of any work you would like considered for extra credit in your README file. Undocumented or poorly-documented extra credit features risk receiving no credit.

Reminder about Collaboration Policy and Academic Honesty