CS 417 Prelim 2 Solutions

------------------------------------------------------------------------
Problem 1

1.1

[  1       0           0    ]
[  0   sqrt(3)/2     -1/2   ]
[  0      1/2     sqrt(3)/2 ]

1.2

To do this I found a rotation R that takes the vector v = [1,1,1] to the x
axis, then using the similarity transform T = inv(R) R_x(30) R as the answer.

I wrote R as two successive rotations: one about the y axis to bring v to the
x-y plane, then one around the z axis to bring it down to the x axis.  The
angle of the first rotation is +45 degrees (that's clockwise when the z axis
is pointing at you).  That brings [1 1 1] to [sqrt(2) 1 0], so the angle of
the second rotation is -asin(sqrt(1/3)), but we don't need to compute the
angle to solve the problem.  Let the angle be theta; then

  sin(theta) = sqrt(1/3)
  cos(theta) = sqrt(1 - sin^2(theta)) = sqrt(2/3)

So T = R_y(-45) R_z(theta) R_x(30) R_z(-theta) R_y(45) = 
 
[  s(1/2)  0 -s(1/2) ] [ s(2/3)  -s(1/3)  0 ] [ 1    0        0    ]
[    0     1    0    ] [ s(1/3)   s(2/3)  0 ] [ 0  s(3/4)  -s(1/4) ] *
[  s(1/2)  0  s(1/2) ] [   0        0     1 ] [ 0  s(1/4)   s(3/4) ]

   [  s(2/3)  s(1/3)  0 ] [  s(1/2)  0  s(1/2) ]
   [ -s(1/3)  s(2/3)  0 ] [    0     1    0    ] 
   [    0       0     1 ] [ -s(1/2)  0  s(1/2) ] 

where s(x) stands for sqrt(x).  s(1/4) and s(3/4) are 1/2 and s(3)/2; I'm
just writing them that way for consistency with the other rotations.

It's pretty easy to multiply the two outer rotations on paper to get the
simpler form:

[  s(1/3) -s(1/6) -s(1/2) ] [ 1    0        0    ] [  s(1/3)  s(1/3)  s(1/3) ]
[  s(1/3)  s(2/3)    0    ] [ 0  s(3/4)  -s(1/4) ] [ -s(1/6)  s(2/3) -s(1/6) ]
[  s(1/3) -s(1/6)  s(1/2) ] [ 0  s(1/4)   s(3/4) ] [ -s(1/2)    0     s(1/2) ]

Another way to do this problem is to construct the rotation by constructing
an orthonormal basis around the rotation axis:

u = [1 1 1]
w = u x [0 1 0] = [-1 0 1]  ([0 1 0] is an arbitrary choice)
v = w x u = [-1 2 -1]

normalizing the three vectors and stacking them up into a basis matrix B:

              [  s(1/3) -s(1/6) -s(1/2) ]
B = [u v w] = [  s(1/3)  s(2/3)    0    ]  (note that sqrt(2/3) = 2 / sqrt(6))
              [  s(1/3) -s(1/6)  s(1/2) ]

this matrix takes the x axis to the direction [1 1 1], and you'll note it is
the same as the leftmost matrix above.  The answer is then 

  B R_x(30) B^T

(transpose because the inverse of an orthonormal matrix is its transpose). 


1.3

The unit-length look direction is [ 0 -3 -4 ] normalized to [ 0 -0.6 -0.8 ].
It's clear by inspection that the vertical axis of the camera is
[ 0 0.8 -0.6 ] (since the camera and the origin are in the y-z plane, the
vertical axis will be also).  The view matrix is supposed to map these two
vectors to the -z and +y axes, respectively, and take the point [0 3 4] to
the origin.  It is easier to write down the inverse of this matrix, which is
the frame matrix for the camera.  Taking the inverse of that matrix, the
answer is:

[ 1    0    0   0 ] -1
[ 0   0.8  0.6  3 ]
[ 0  -0.6  0.8  4 ]
[ 0    0    0   1 ]

or

[ 1    0    0   0 ]
[ 0   0.8 -0.6  0 ]
[ 0   0.6  0.8 -5 ]
[ 0    0    0   1 ]

A lot of people thought that the up vector was supposed to be the actual
vertical axis of the camera.  The from/at/up camera notation was only covered
once in lecture so a correctly built oblique projection got nearly full
credit for this part.


1.4

First way: use the projection plane z = -1.  This means we start with the
matrix:

[ 1  0  0  0 ]
[ 0  1  0  0 ]
[ 0  0 -1  0 ]

Sketching out a right triangle indicates that the half-height of a 60 degree
image is 1/sqrt(3), so the half-width at aspect 1.5 is 3/(2*sqrt(3)).  Since
we want the image half-height and half-width to be 1, we need to scale along
the x and y axis, leading to the final projection matrix:

[ 2*sqrt(3)/3     0      0  0 ]
[      0       sqrt(3)   0  0 ]
[      0          0     -1  0 ]

Second way: use the image height 2.  The right triangle tells us that the
focal length is d = sqrt(3).  Now we just need to scale by 1/aspect in the x
direction.

[ 2/3  0       0      0 ]
[  0   1       0      0 ]
[  0   0  -1/sqrt(3)  0 ]

These matrices are completely equivalent because they are scalar multiples of
one another.



------------------------------------------------------------------------
Problem 2

2.1
      C1 C2 conv interp
Herm   Y  N   N     Y
Bez    Y  N   Y     N
QBsp   Y  N   Y     N
CBsp   Y  Y   Y     N
C-R    Y  N   N     Y 


2.2

(a) see sketches
(b) C^inf, G^0
(c) t = 0.5 -- by symmetry
(d) see sketches
    you can tell the cusp occurs because both derivatives are zero at the
    same time
(e) alpha = 1

Derivation: Most people probably had written down the spline matrix

  [ -1  3 -3  1 ]
  [  3 -6  3  0 ]
  [ -3  3  0  0 ]
  [  1  0  0  0 ]

We need to know the value of a for which x'(1/2) is zero.  The control point
vector for the x coordinate is [ -1 a -a 1]^T.  Multiplying this by the
matrix we get

         x(t) =  (6a+2) t^3 -  (9a+3) t^2 + (3a+3) t + 3
        x'(t) = 3(6a+2) t^2 - 2(9a+3) t   + (3a+3)
  0 = x'(1/2) = (3/4)(6a+1) -  (9a+3)     + (3a+3)
              = -(3/2)a + (3/2)
            a = 1

It's a bit more algebra, but you can also work this out if you remember that
the derivatives at the endpoints are 3 times the vectors between the control
points, leading to x'(0) = x'(1) = 3(a+1).


------------------------------------------------------------------------
Problem 3

3.1 The farther away viewpoint sees more of the surface.

Each viewpoint can see the part of the surface inside the cone from the
viewpoint tangent to the sphere; for very far away viewpoints you can see
almost a full hemisphere but when you are closer you see less.

3.2 (ii)

As illustrated by part 3.1, the man looks different if he is standing far
away or nearby; scaling the large image produced by the man standing nearby
so that it matches the height of an image of the man standing far away is not
going to make the two pictures match.  So (i) and (ii) are different.
However, scaling up the man while changing the distance to compensate does
not change the image.  So (i) is the same as (iii). 

3.3 Since their heads are the same size but the images of the heads are in the
ratio 6:1, the distances to the two people are in the ratio 6:1.  The closer
person's head is 1/5 of the height of the image, so the overall height of the
image at the plane where the near person is standing is 5 * 30cm = 1.5 meters.
Then by similar triangles 24mm:(focal len) = 1.5m:(near person
distance). Since the focal lengths are 1, 2, and 4 times the image height, the
distances for the near person are 1.5, 3, and 6 meters.  The far person is 6
times as far away, or 9, 18, and 36 meters.


------------------------------------------------------------------------
Problem 4

4.1

vertices:

0:  0  0  1
1:  0  0 -1
2:  0  1  0
3:  0 -1  0
4:  1  0  0
5: -1  0  0

triangles:

0 2 4
5 2 0
1 2 5
4 2 1
4 3 0
0 3 5
5 3 1
1 3 4


4.2

first collapse: 0 -- 4
second collapse: 1 -- 2

The only trouble you can get into here is if you do a bad edge collapse as
the second operation (for instance, collapsing two of the edges around the
"equator").


4.3

You can recognize the unsafe ones because they are opposite vertices of
valence 3.

The left, back, and bottom face diagonals are unsafe.
The right, front, and top face diagonals are safe.


4.4

You can fix the problem by swapping the left, back, or bottom diagonal to
split the face the other way.  Then all vertices have valence >= 4.