# CS4620 PA6 Animation

Out: Friday November 13, 2015

Due: Friday November 20, 2015 at 11:59pm

Do the programming part in groups of two.

Do the written part alone.

### Introduction

In this assignment, we will explore a common topic in animation: key frame animation. You will solve some written problems (by yourself) to get a better understanding of the underlying theory of animations and then write code to animate scenes using key frames. Key frame animation is a technique wherein we define the layout of a scene at certain times (key frames), and we create frames between them by cleverly interpolating between our defined key frames. This rapid rendering of scenes gives us the illusion of animation. The award winning animation short film Hunger (1974) was one of the first applications of key frame animation. http://bit.ly/1EDvU6R

### Problem 1: Keyframe Animation

#### Getting Started

For the programming assignment, we will implement the primary features of a keyframe animation framework. A new commit has been pushed to the class Github page in the master branch. We recommend switching to your master branch, pulling this commit, and creating a new branch (e.g. A6 solution) and committing your work there. This new commit contains all the framework changes and additions necessary for this project. For this project, we use lwjgl, so you may need to update some settings of your build to have this external library work properly. We have included the correct jar files, but you may need to configure your native library location. To do this in Eclipse, go to Project -> Properties -> Java Build Path -> Select Libraries -> Select the lwjgl Drop Down Menu -> Modify Native Library Location. Modify this setting so that it matches your OS. We have added a framework in the package cs4620.anim that stores keyframes and provides an interface for editing them; you will build on that framework and implement a few main features that enable correct interpolation of animations between keyframes.

#### The Interface

At first glance, your window may not like the one in the picture. Hover over the bottom of the window to reveal the timeline, complete with highlighted keyframes. We have implemented a keyboard based animation interface:
• Moving between frames: [ ] We use the [ and ] keys to move to the left and right keyframes.
• Adding a frame: To add a keyframe at the current frame, press the n key. The new keyframe will be initialized to the current state of the scene when you clicked the button.
• Editing a keyframe: To edit a keyframe, navigate to that keyframe, edit the transformations at that state, and press n.
• Removing a keyframe: Navigate to a keyframe and press the m key to remove a key frame.
• Playing and pausing the animation: The \ key is used to play or pause the animation.

#### Keyframes

For this problem, we have extended the scene graph system to store information about multiple keyframes. The AnimTimeline class stores a:
• TreeSet of AnimKeyFrame. Each key frame contains a frame index number and a 4 x 4 matrix transformation.
• A SceneObject that it operates on.
Every time the update loop is called in the Game loop, updateTransformations is called in AnimationEngine which sends transformation events to the corresponding SceneObjects. We have already implemented the functionality of adding and deleting keyframes from the scene.

#### What You Will Do

• Implement void updateTransformations() - A method that iterates through all the animation timelines, and calls sendEvent on the scene with the correct interpolated transformation on the object. For example, if the object on the AnimTimeline is called object, then scene.sendEvent(new SceneTransformationEvent(object)); would begin the propagation of the event.
• Create Animation - After completing this short coding assignment use one of the included scenes to create an interesting animation. This should showcase all of your working transformations (rotation, scaling, and translation). Screen capture your animation and include this video in your submission.

#### Interpolation Overview

##### Naive Approach
When computing the interpolation of two transformations, the naive approach is to linearly interpolate each of the 12 free values of the 4 x 4 matrix. You may want to try this out and see why this doesn’t work so well. See what happens when you rotate an object 180 degrees!
##### The more accurate approach
Linearly interpolating rotations by value does not work very well. While scales and translations can be linearly interpolated to give good results, the same doesn’t apply to rotations. So what can we do? It turns out there is a good way to interpolate between two pure rotations: first express the rotations as quaternions, then use a method called slerp, or spherical linear interpolation, to interpolate between the quaternions. Therefore, the general idea for a more accurate interpolation is:
• Decompose the surrounding 4x4 matrix transformations around the current key frame into rotations, translations, and scales.
• Linearly interpolate the translations and scales, and interpolate the rotations by converting to quaternions, slerping, and then converting the result back to a rotation matrix.
• Recompose the constituents to give a transformation for the current frame.
##### Decomposing transformations
A homogenous transformation M is a 4x4 matrix that can be decomposed firstly as follows $$\begin{pmatrix} RS & T \\ 0 & 1 \end{pmatrix}$$ Here, $T$ represents the translation, $R$ the rotation and $S$ the scale. So just how do we decompose the upper left 3x3 portion of the matrix into its constituents? Polar decomposition. We have conveniently written the egl.math.Matrix3.polar_decomp function for you. There is more about quaternions, spherical linear interpolation, and the polar decomposition, in the Animation lecture slides and notes, and in Chapter 17 of the textbook.

#### Slerp

Spherical linear interpolation occurs between quaternions, so we need to convert our representation of $R$ as a 3 x 3 matrix into a quaternion for each keyframe, and then convert the interpolated quaternion back to a matrix.
##### Converting between Rotation Matrices and Quaternions
We do not ask you to implement the inter-conversion between rotation matrices and Quaternions. You can use the class egl.math.Quat to convert from a rotation matrix (using the appropriate Quat constructor) and to a rotation matrix (using the toRotationMatrix method). Feel free to look at the code to understand how it works if you’re interested. All you need to know about Quaternions is that they are 4-vectors, and that unit-length quaternions, called unit quaternions, can represent 3D rotations and also interpolate them well. If you want to learn more, take CS 5625 next semester!
##### Linear Interpolation
Typically, we visualize quaternions as vectors that represent rotation. Yes, they have 4 numbers, but as most things with higher dimensionality, imagine them to be in a lower dimensional space, say 2D, and say “four” to yourself. Given two quaternions $q_1$ and $q_2$, and a $t$ to interpolate such that $0 < t < 1$, a linear interpolation, or lerp, q is given by: $$q = (1 − t)q_1 + tq_2$$ This will work, if we normalize the interpolated quaternion so that it’s a unit quaternion again, but unfortunately the rotation does not happen at constant speed—it will go faster towards t=0.5 and slower towards the ends.
##### Spherical Linear Interpolation
Intuitively, spherical linear interpolation, or slerp, gets around this problem by interpolating these quaternions (read: vectors) along the sphere they are both a part of. We’ll avoid the details of the derivation of the slerp formula, which are in the lecture slides. Let’s just review how slerp is calculated. Given quaternions $q_1$ and $q_2$ at the surrounding key frames and an interpolation ratio $t$ such that $0 < t < 1$, we first calculate the angle between $q_1$ and $q_2$, called $\Omega$, as follows: $$cos \Omega = q_1 \cdot q_2$$ Then the interpolated quaternion q is given by $$q =\frac{sin(\Omega − t\Omega)}{sin\Omega}q_1 + \frac{sin (t \Omega)}{sin \Omega}q_2$$ We have implementated this in the egl.math.Quat.slerp function for you as well.

### Demo Video

This short video shows what to expect after correctly completing the coding portion of the assignment.

### What to Submit

Submit a zip file containing:
1. Your solution organized the same way as the code on CMS. Please include your .classpath and .project in the submission as well as all the pre-existing files in the codebase, and not merely your modified files.
2. Your animation video.
3. A readme file containing
• You and your partner’s names and NetIDs.
• Any problems with your solution.
• Anything else you want us to know.