CS 417 Homework 4 Solutions
------------------------------------------------------------------------
Problem 1
1.1.
The child should be placed at 20/6 meters from the camera.
The man should be placed at 2*20/6 meters from the camera.
1.2.
Let f be the focal length.
Let theta be an angle such that
tan(theta) = height of the house / distance of that house from the camera = 6/20.
Then tan(theta) also = (3/4*12 mm) / f
Or f = (3/4*24 mm) / tan(theta)
= (3/4*24 mm) / (6/20)
= 60 mm
1.3.
We are zooming out while moving down.
Let theta be half the vertical field-of-view of the camera.
Let w be the height of the image at the relevant floor (w = 4/3 * 3 meters = 4 meters)
Let d be the distance from the camera center to the relevant floor
by trigonomery:
tan(theta) = (w/2) / d = w / 2d
therefore
d = w / (2 tan(theta)) = 2 meters / tan(theta)
and, since the relevant floor is 6 meters from the ground,
camera height = 6 meters + 2 meters / tan(theta).
Since 2 theta is spec'd to change linearly from 10 to 60 over 5 seconds,
theta = 5 + 5 t
and the answer is
camera height = 6 meters + 2 meters / tan(5 + 5 t).
------------------------------------------------------------------------
Problem 2
2.1.
a. two-point
b. orthographic
c. one-point
d. oblique
e. three-point
2.2.
Let l stand for lambda.
[1 0 0 1]
[l1x1 l2x2 l3x3 l4x4] = M [0 1 0 1]
[0 0 1 1]
Therefore:
M = [l1x1 l2x2 l3x3] (*)
[1]
M [1] = l4x4
[1]
Let l4 = 1, and we have l1x1 + l2x2 + l3x3 = x4 or
[ | | | ] [ l1 ] [ | ]
[ x1 x2 x3 ] [ l2 ] = [ x4 ]
[ | | | ] [ l3 ] [ | ]
This is a square linear system,
So now we can solve for l1, l2, and l3.
Then we can to get M from (*).
Let's call the matrix M T(x1,x2,x3,x4).
Then the answer to this problem is T(q1,q2,q3,q4) T(p1,p2,p3,p4)^-1.
------------------------------------------------------------------------
Problem 3
Suppose we want to collapse vi and vj. We will be in trouble if there are
vertices that are adjacent to both vi and vj other than the two that we
expect, namely the third vertices of the two triangles on either side of the
edge vi -- vj. Two examples of unsafe cases are a triangular prism tube that
is being collapsed and the case where one of the vertices opposite the edge
has valence 3.
Here is one way to enumerate and compare the sets:
for every triangle (vi v1 v2) incident on vi
for every triangle (vj v3 v4) incident on vj
if v2 != vj && v4 != vi && v1 == v3
Warn("collapsing will make the mesh non-manifold")
This code is a teeny bit subtle because it does visit the allowed vertices;
it visits one of them for vi and the other for vj so they will not ever
match. It's also slightly loose pseudocode because it implicitly rotates
the triangles so that vi and vj are first. A slightly more explicit version:
for every triangle ti incident on vi
v1 = successor of vi in ti
v2 = predecessor of vi in ti
for every triangle tj incident on vj
v3 = successor of vj in tj
v4 = predecessor of vj in tj
if v2 != vj && v4 != vi && v1 == v3
Warn("collapsing will make the mesh non-manifold")
where successor and predecessor are defined mod 3.
Note that this will allow an edge of a tetrahedron to be collapsed, resulting
in a pair of back-to-back triangles (which is still a manifold mesh by my
criteria) and then an edge of that mesh to be collapsed resulting in the
disappearance of the entire thing (which is vacuously a manifold because it is
empty).
Here is another way of saying this:
Si = set of vertices adjacent to vi
Sj = set of vertices adjacent to vj
if size(Si intersect Sj) > 2
Warn("bad news!")
We know that the two safe vertices will end up in the intersection (with the
sole exception of the back-to-back case, but then there can be no other
triangles attached to anything so we needn't worry), so if there are unsafe
vertices in common the size of the intersection will have to be > 2.
Another nice solution: look at each vertex vk that is adjacent to vi or vj. Count
the number of triangles incident on vk that are also incident on vi or vj.
If the number is > 3 then we are in trouble, otherwise OK.
------------------------------------------------------------------------
Problem 4
The sketches that go with this part are an example of what one might hope to
achieve in one try with a non-erasable writing instrument.
4.1.
The cross section is the 1D B-spline basis function (looks similar to a
gaussian)
[see also hw4-sol-sketches.jpg]
4.2.
dp(s,t)/ds = sigma(i,j) b'(s-i) b(t-j) pi,j
dp(s,t)/dt = sigma(i,j) b(s-i) b'(t-j) pi,j
where b(x) =
x^3 for 0 <= x <= 1
-3(x-1)^3 + 3(x-1)^2 + 3(x-1) + 1 for 1 <= x <= 2
3(x-2)^3 - 6(x-2)^2 + 4 for 2 <= x <= 3
-(x-3)^3 + 3(x-3)^2 - 3(x-3) + 1 for 3 <= x <= 4
0 otherwise
where b'(x) =
3x^2 for 0 <= x <= 1
-9(x-1)^2 + 6(x-1) + 3 for 1 <= x <= 2
9(x-2)^2 - 12(x-2) for 2 <= x <= 3
-3(x-3)^2 + 6(x-3) - 3 for 3 <= x <= 4
0 otherwise
4.3.
It is the cross product of the two tangent vectors
dp(s,t)/ds x dp(s,t)/dt
4.4.
Yes. The cross section looks like 2 b-spline basis functions
(1 upright and the other upside-down).
The other cross section looks a little like a sine function but is smooth at
the ends.
[see also hw4-sol-sketches.jpg]
4.5.
No, because it is no longer a linear function of control points.
That is, there are terms with pi,j * pk,l.