## Description

## Part A [50 marks in total]

Below are different exercises covering different topics from the first weeks of class. They require thought, so

you are advised to consult the relevant sections of the textbook, the online lecture notes and slides, and

your notes from class well in advance of the due date. Your proofs and derivations should be clearly written,

mathematically correct, and concise.

All questions require showing the steps toward the solution, and marks will be subtracted if this is not

the case. Even if you cannot answer a question completely, it is very important that you show your

(partial) answers and your reasoning. Otherwise your TA will not be able to award you partial marks.

Both Part A and Part B must be electronically submitted. Part A must be in PDF format, by scanning

your handwritten solution or by using LaTeX/word to typeset it.

## Points & Polygons [10 marks total]

1) Suppose the vertices of a convex polygon are ̅̅ ̅, ̅̅ ̅,…, ̅̅ ̅, given in counter-clockwise order. Let the

coordinates of vertex ̅ be (

,

).

(a) [3 marks] Express the coordinates of the inward-facing normal

⃗⃗⃗ at

̅̅̅ ̅ ̅̅

̅ ̅̅ ̅

in terms of the

coordinates of vertices ̅ and ̅̅ ̅ ̅̅ ̅.

(b) [3 marks] Let ̅ be an arbitrary point on the 2D plane, let be the line containing ̅

and ̅̅ ̅ ̅̅ ̅, and let

⃗⃗⃗ be the normal in (a). Give a test that determines whether point ̅ is on the

same (inward-facing) side of as

⃗⃗⃗ .

(c) [4 marks] Describe an algorithm that can tell whether a 2D point ̅ is inside the shaded region in

the figure. You should assume that the polygons defined by vertices ̅̅ ̅, ̅̅ ̅,…, ̅̅ ̅ and ̅ , ̅ ,…,

̅̅ ̅, respectively, are both convex. Hint: Each edge is contained in an infinite line that divides

the 2D plane into two half-planes. The key insight is that the interior of a convex polygon is the

intersection of the left half-planes of all the edges in the polygon.

## Transformations [20 marks total]

2) [8 marks] Two transformations f1 and f2 commute when f1○ f2 = f2○ f1. For each pair of

transformations below, specify whether or not they commute. In each case, your solution can either be

a derivation that proves/disproves commutativity, or if f and g do not commute, a specific counterexample.

(a) Translation and uniform scaling

(b) A rotation about the origin and a uniform scaling

(c) A rotation about the origin and a non-uniform scaling

(d) A shear with respect to the x-axis and a shear with respect to the y axis

3) Shears

(a) [6 marks] Prove that a shear in y can be created with a combination of rotations and shears in

x.

(b) [6 marks] Show that any 2D rotation can be achieved as a series of 3 consecutive shears.

## Curves [20 marks total]

4) [10 marks] The revolution of a planet around its star is proposed to be a super-ellipse in 2D having the

following parametric form:

Find the tangent vector and normal vector to the super-ellipse as a function of the time t. What is the

area and perimeter of this super ellipse? Sometimes there is no closed-form answer to attributes like

area and perimeter. How can we compute these approximately, for a closed parametric curve?

5) [10 marks] A projectile launched from a cannon on a cliff located at (0, h) follows a trajectory given by

the parametric equations:

x(t) = at

y(t) = – ½gt2 + bt + h

where the initial velocity is (a, b), g is the gravitational constant, h is the height of the cliff, t is in [0,

ti] and is the free parameter corresponding to time, and ti

is the time of impact with the ground which

corresponds to y=0.

(a) [4 marks] Give expressions for the tangent and normal vectors of the projectile trajectory as a

function of t.

(b) [6 marks] Give an expression for the time of impact ti

. Also give expressions for the location

and velocity at the time of impact.

Read on for PART B >>>

## Part B: Animating a Hierarchical 2D Object [50 marks in total]

The figure below shows an articulated nine-part, seven-degree-of-freedom (DOF) planar robot penguin:

mouth closed

It has six rotational joints (depicted by circles), each with one rotational degree of freedom. The beak

has a single translational degree of freedom: the beak can only move up or down (in the coordinate frame

of the head). Your task will be to render and animate such a robot penguin using OpenGL.

Hierarchical objects like this are often defined by specifying each part in a natural, part-based coordinate frame, along with transformations that specify the relative position and orientation of one part with

respect to another. These transformations are often organized into a kinematic tree (e.g., with the torso as

the root, and the jaw as a leaf). In addition to the kinematic tree, one must also specify the transformation

from the root (e.g., the torso) to the world coordinate frame.

Then, for example, to draw the torso you

transform the points that define the torso from the torso’s coordinate frame to the world coordinate frame,

and then from the world coordinate frame into device coordinates. Then to draw an arm, you must transform the points that define the arm in the arm coordinate frame to the torso’s coordinate frame, and then

from the torso’s coordinate frame to the world coordinate frame, and then into device coordinates. And so

on down the tree.

Rendering articulated objects is easiest if a current part-to-device mapping is accumulated as you

traverse the object/part hierarchy. You maintain a stack of coordinate transformations that represents a

sequence of transformations from the current part coordinates up through the part hierarchy to world

coordinates, and finally to device coordinates. For efficiency, we do not apply each of the transformations

on the stack in succession. Rather, the top of the stack always represents the composition of the preceding

transformations. OpenGL provides mechanisms to help maintain and apply these transformations.

## Your Programming Task

Your task is to design and render the articulated robot penguin using OpenGL. When the program is run,

the robot should move (i.e., animate) in order to help test that the rendering is done correctly.

To accomplish this, you must perform the following basic tasks:

(a) [5 marks] Design the parts in terms of suitable generic shapes and deformations, and

draw them using OpenGL.

(b) [10 marks] Design and implement suitable transformations that map each part’s local

coordinate frame to the coordinate frame of its predecessor in the kinematic tree. Extend

the GUI with additional spinners to control each of the 9 degrees of freedom (DOFs).

Hint: The interactive DOF controls will be useful in debugging the transform hierarchy

you build.

(c) [10 marks] Design and implement a set of functions that will control the animation, i.e.,

will control the state of each joint in each frame. You can use simple functions such as

sinusoids to define the way in which parts move with respect to one another. Or, if you

wish, you could specify a sequence of specific joint angles that the rendering will loop

through. You can also use key-framing to specify a few key poses for the penguin (in

terms of the joint angles) and linearly interpolate between them for smooth animation.

Hint: You can use the GUI build for (b) to choose the set of key-frames or help you

specify the values for the joint angles that produce the desired animation.

(d) [15 marks] Put it all together to generate your animation, by drawing each part in turn as

you descend the kinematic tree (once per frame). Use the OpenGL transformation stack

to control relative transformations between parts, the world and the display device. It

is not necessary to write code that could be used to render arbitrary articulated objects,

thereby requiring that your code can traverse any kinematic tree. To keep things simple,

you may hardcode the sequence of parts that are drawn.

(e) [2 marks] Be sure to also draw the small circles which depict the locations of the rotary

joints.

(f) [8 marks] Explain everything you did in a written report (see below).

## Helper Code

To get started, we have created a simple demo for you. This will show you how to use the very basic

commands of OpenGL to open a window and draw some basic shapes. It will also provide you with a

template Makefile for compilation and linking of your programs.

This simple demo program opens a window, and animates a two squares connected by a hinge. To

unpack, compile and run this demo on CDF, download the file a1.tgz and use the following commands

tar xvfz a1.tgz

cd a1/penguin

make

penguin

Compilation

To compile programs easily we have set up a simple makefile for you, that builds the executable using the

make command you issued above. Make searches the current directory for the file called Makefile which

contains instructions for compilation and linking with the appropriate libraries.

You will find this Makefile useful when compiling programs for your later assignments. For example,

if you wish to compile a program with a different name, change all occurrences of penguin to the name of

the file you wish to compile. You can also change the Makefile to include code from several files by listing

the C++ source files(i.e., the files ending in .cpp) on the line CPPSRCS=. The name of the executable file

is determined by the name you use in the Makefile on the line PROGRAM = penguin.

When you run the demo program a graphics window will appear. The size of the window is determined

by parameters (xmax and ymax) to the initialization routine. Each pixel is indexed by an integer pair

denoting the (x, y) pixel coordinates with (0,0) in the top left hand corner and (xmax,ymax) in the bottom

right.

## Turning in your Solution to Part B

All your code should remain in the directory a1/penguin. In addition to your code, you must complete the

files CHECKLIST and REPORT contained in that directory. Failure to complete these files will result in

zero marks on your assignment.

The REPORT file should be a well-structured written (or diagramatic) explanation of your design,

your part descriptions, and your transformations. The description should be a clear and concise guide to

the concepts, not a simple documentation of the code. In addition to correctness, you will also be marked

on the clarity and quality of your writing. We expect a well-written report explaining your design of parts

and transformations.

Note that this file should not be thought of as a substitute for putting detailed comments in your code.

Your code should be well commented if you want to receive full (or even partial) credit for it.

To pack and submit your solution, execute the following commandsfrom the directory containing your

code (i.e., a1/penguin):

cd ../../

tar cvfz a1-solution.tgz a1

submit -c csc418h -a A1b a1-solution.tgz (if registered for CSC418)

submit -c csc2504h -a A1b a1-solution.tgz (if registered for CSC2504)

Compatibility

All of your assignments must run on CDF Linux. You are welcome, however, to develop on other platforms (and then port to CDF for the final submission). This sample code is designed to work on Linux

and Mac OS X machines, but should be portable to other Unix platforms (including Windows with Visual

C++). If you are running your own machine, it almost certainly has OpenGL installed; if not, you can

search for an rpm or go to http://www.opengl.org/(see their getting started FAQ).

If you are planning to develop for windows with Visual C++, we have included some starter code

to help you out. Unpack the starter code and place the unpacked files and the include directory in your

a1/penguin directory. You will then need to add the skeleton code to your Visual C++ project.

If you develop on a different platform, be sure you know how to compile and test your code on

CDF, well before the deadline. Your assignment must run on the CDF Linux configuration. Several

marks will be deducted if your code does not compile and/or run without modification. If the marker

cannot easily figure out how to compile and execute the code, it will most likely receive zero marks. If you

choose to develop the assignment in MacOSX or Windows, test porting your code to Linux long before

the deadline, perhaps even before you have finished the assignment. Often bugs that are “hidden” when

compiling on one platform, make their presence known by crashing the application on a different platform.

We will not be sympathetic to porting problems that you have at the last minute.