PSet 2: Transformations & Polygons

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
.
.