Project Three


Project 3: Virtual Mannequin

Assigned: Tuesday, Oct 18, 2016
Due: Thursday, Nov 10, 2016 (by 11:59PM)

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

As before, we have provided you with starter code, written in C++ and using Open GL and several OpenGL helper libraries (glm, glfw) as a starting point for implementing this project. We have also included code for reading and writing images to JPEG files (this requires a nontrivial amount of low-level parsing and byte manipulation). The starter code is a working example of how to set up OpenGL and a shader program to draw a checkerboard floor, and move around the world using an orbital and FPS camera (as per assignment 2). We have also provided a reference solution of how this project should function if you implement it correctly. The program responds to keyboard and mouse input as specified below. If you have questions or doubts about how your program should behave, the reference solution is a first place to check.

Building and Running the Starter Code

We have provided cmake scripts to automate compiling and running the assignment code. Please do not modify the build process as it has been designed to streamline grading. To compile your code, type
mkdir build
cd build
cmake ..
to generate an executable in the bin subdirectory. For additional information about the starter code, please see the included file.

Submission Instructions

All submissions must be uploaded to Canvas by the project due date and time. In exceptional cases where Canvas is not working, you may turn in the assignment by emailing the TA a Dropbox link, handing him a USB stick, etc, but there will be no exceptions to the project due date--late submissions will be penalize per the syllabus late policy. Submit your project as a single .tgz file. This file should be free of temporary files, core dumps, etc; you also should not submit the (large) mesh files included in the starter code. For example, you can execute the following command from the parent folder containing the code to create an appropriate .tgz file:
tar --exclude obj --exclude build --exclude ".*" -czf submission.tgz foldername
where foldername is the name of the folder containing your code. In addition to your complete source code, the .tgz file should include a README file containing, at minimum: All code ***MUST*** compile and run on the 3rd floor GDC computer lab Linux machines!!!

In particular,

Please triple-check that your submission adheres to these instructions. The instructor or TA reserves the right to return, ungraded, any submissions that fail to compile or run, or that do not include a README file.

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.


The assignment is broken down into several features described below. Each feature is worth a number of points and will be graded separately (although later feature may build on and require a working implementation of earlier features). Your code should be correct and free of segfaults, deadlocks, or other buggy behavior. You will not be graded on software engineering (use design patterns and unit tests if they help you) but unreadable code is less likely to receive partial credit. You should not worry too much about performance or optimizing your code, but egregiously inefficient implementations of any of the features will be penalized.

Required Features (150 points)

Parsing the Joints and Weights (30 points)

All data related to a character is stored in a PMD file. This file contains the model itself - represented as a triangle mesh along with some information about the materials and textures to use for that mesh - as well as a skeleton rig and blending weights specifying how moving the bones affects the different parts of the model.

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

Notice that several joints might share the same parent - this represents a branching in the skeleton. For example, several finger joints might specify a wrist joint as its parent.

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

You will represent each bone's coordinate system relative to the parent bone's coordinate system. This way, if you e.g. bend your arm, all child bones (hand, fingers, etc) will bend with it automatically. To do this, build two transformations for each bone:
  1. the translation Ti, 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, Ti 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 Ri which maps the parent coordinate axes to the bone's coordinate axes.
If a bone has no parent, Ti and Ri should be with respect to world coordinates.

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)

As the user moves the mouse around the screen, you should highlight nearby bones; these highlighted bones are then the ones the user will rotate by clicking and dragging the mouse. Implement functionality that determines, whenever the user moves the mouse, which bone should be highlighted: Notes: (ignore these if they are more confusing than helpful)

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.

Cylinder drawing:

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)

When the user clicks and drags the mouse, the camera rotates, as in assignment 2. You will implement a second mode, toggled by pressing the M key, where clicking and dragging the mouse rotates the highlighted bone (and all child bones attached to the highlighted bone) instead. To do this you will track not only the original coordinate system \(R_i\) of each bone, but also the deformed coordinate system \(S_i\) of the bone. Initialize \(S_i = R_i\); as the user rotates the bones, the two will no longer match. Notice that rotating a bone changes \(S_i\), and so implicitly also changes the origin and orientation of all child and descendent bones (just like bending your arm also affects your wrist, fingers, etc.) If you have set up your transformations properly, bones should transform correctly automatically when you change their ancestors.

Linear Blend Skinning (35 points)

You now have all the machinery needed to implement linear blend skinning. The instructions below walk you through how to this using the provided weights in the PMD file, and assuming you will animate the vertex positions on the CPU. You are welcome to implement linear-blend skinning entirely on the GPU instead, for extra credit.

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.

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

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)

When the user hits the J key, save a screenshot to the assignment's root directory. We have provided a routine for doing the image file IO for you, but you will need to look up annd implement how to read pixels from the framebuffer using OpenGL.

Extra Credit (up to 50 points)

Many opportunities for extending the project exist, beyond the basic functionality required above. You may implement additional features for extra credit. Particularly impressive submissions will receive more points, and you may be invited to demo an outstanding entry for the class. Some ideas include Important Any extra credit you attempt must obey the following two cardinal rules:

Reminder about Collaboration Policy and Academic Honesty

You are free to talk to other students about the algorithms and theory involved in this assignment, or to get help debugging, but all code you submit (except for the starter code, and the external libraries included in the starter code) must be your own. Please see the syllabus for the complete collaboration policy.
Last modified: 10/18/16 by Don Fussell