CS 680 PSet 2: Transformations & Polygons

Question 1: (680: 15 pts)

Give pseudo-code for an algorithm to determine if the vertices of a polygon are given in

clockwise (CW) or counterclockwise (CCW) order. You may assume that the polygon is

simple and non-degenerate; it may be concave or convex. As an example of acceptable detail,

here is example pseudo-code for an algorithm that determines if a 2D polygon is concave or

convex:

// Algorithm to determine if a polygon is concave or convex

// Polygon vertices could be provided in CW or CCW order

// Three sequential vertices may be collinear

Input: v[1], …, v[N] // N polygon vertices

Output: True or False // True if convex, False if concave

Vector e1, e2;

float z;

int sign_of_sine_theta=0;

// compute cross-product between successive edges

// if sign of all the z values are all the same, then convex

// loop around polygon, taking cross product at each vertex

for (j=1; j<=N; ++j){

if(j==N)

k=1;

else

k=j+1;

if(j==1)

i=N;

else

i=j-1;

e1= v[j]-v[i];

e2= v[k]-v[j];

z = (e1.x * e2.y) – (e2.x * e1.y); // z of cross-product

if(z < 0.0){

if(sign_of_sine_theta > 0)

return False; // sines with different signs

else

sign_of_sine_theta = -1;

}

else if (z > 0.0){

if(sign_of_sine_theta < 0)

return False; // sines with different signs

else

sign_of_sine_theta = 1;

}

}

Submission guidelines:

Please prepare your answers neatly written or typed. Submit electronically on Gradescope. If

you have prepared hand-written solutions, please still submit online by uploading a scan or

photograph. Acceptable formats are .pdf (preferred), .jpg or .png.

return True;

a) Main question: Consider the case when the input to the algorithm is a sequence of

polygon vertices and a point known to be within the interior of the polygon (inside the

polygon, and not on the boundary). To simplify things, you may assume we have a

function βsegsIntersect(p1, q1, p2, q2)β which will return a boolean telling you whether

the line segments from p1 to q1 and p2 to q2 intersect.

b) Extra credit (5 pts): Suppose the point in the interior of the polygon is not provided.

Describe a strategy for finding such a point. Pseudocode not required.

c) Extra credit (10 pts): Look up the βshoelace formulaβ for the area of a polygon. Can you

come up with an alternate algorithm based on this formula? Pseudocode needed here.

Question 2: (680: 20 pts)

(a) Write a 4 x 4 homogeneous transform matrix M that when applied to a point

π = (π₯, π¦, π§, 1) yields π

α± = (π₯α±

, π¦α±

, π§α±

, 1) where

π₯

α± =

1

β2

π₯ β

1

β2

π§ + π

π¦

α± = 3π¦ + π

π§

α± = β

1

β2

π₯ β

1

β2

π§ + π

(b) What three or four basic computer graphics transforms occur when applying M to a 3D

point? In other words, how can you decompose M into transforms such as scaling,

rotation, translation? Give a homogeneous transform matrix for each, and show the order

in which they are multiplied.

Question 3: (680: 10 pts)

Derive the shear matrix that would transform the block βhβ character on the left to the italic

βhβ character on the right. Show your answer first with variables, then replace the variables

with values for your final answer.

Question 4: (680: 20 pts)

Consider the following unit quaternions

πΰ¬΅ = (0, 0,

1

2

,

β3

2

)

πΰ¬Ά = (

β3

2

, 0, β

β3

4

,

1

4

)

a) πΰ¬΅ represents a rotation of angle πΰ¬΅ about a unit vector π’ΰ¬΅. What is this angle and vector?

(Note: there are several acceptable answers).

b) πΰ¬Ά represents a rotation of angle πΰ¬Ά about a unit vector π’ΰ¬Ά. What is this angle and vector?

(Note: again, several acceptable answers).

c) Does rotation by πΰ¬΅ and πΰ¬Ά commute? Why?

d) Extra credit (5 pts): When do two rotations commute? When do they not? Prove these

statements. (Hint: consider the equation for quaternion multiplication).

Question 5: (680: 15 pts)

Derive a 3D homogeneous transformation matrix to scale along the u-axis with origin C by

Su. Your solution should not use trigonometric functions for Rin or Rout, instead use the

orthonormal basis vectors as discussed in class.

Question 6: (680: 20 pts)

Derive a homogeneous transformation matrix that can be used to reflect 3D points about a

plane with equation ax + by + cz = d. Your solution should not include the explicit

computation of any Euler rotation matrices Rx, Ry, and Rz.

.

C

.

C

.

z

.

z

.

.