Sale!

# PSet 2: Transformations & Polygons

\$35.00

Category:

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

PSet 2: Transformations & Polygons
\$35.00
Hello
Can we help?