CS680-PSet 2: Transformations & Polygons Solved

Question 1:   (680: 

      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;

                            }

}

return True;

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

Write a 4 x 4 homogeneous transform matrix M that when applied to a point 𝑝 = (𝑥, 𝑦, 𝑧, 1) yields 𝑝 = (𝑥 , 𝑦 , 𝑧 , 1) where 
𝑥  𝑧 + 𝑎

𝑦 = 3𝑦 + 𝑏

𝑧  𝑧 + 𝑐

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: 

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:

      Consider the following unit quaternions

                                                                                  𝑞  

                                                                              𝑞    , 0, −

 

𝑞 represents a rotation of angle 𝜃 about a unit vector 𝑢 . What is this angle and vector? (Note: there are several acceptable answers).
𝑞 represents a rotation of angle 𝜃 about a unit vector 𝑢 . What is this angle and vector?
(Note: again, several acceptable answers).

Does rotation by 𝑞 and 𝑞 commute? Why?
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:

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: 

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.