CS465 Fall 2004 -- Final Exam solution Steve Marschner ------------------------------------------------------------------------------ Problem 1: Filtering & Resampling (20 pts) ------------------------------------------ 1.1 I will filter horizontally, then vertically. In separable filtering we filter the rows independently, so the rows of zeros remain zeros and the rows with ones are both the same. The sampling pattern looks like this: 0 0 1 1 0 0 ... ^ ^ ^ ^ ^ ^ ^ ^ ^ ... 0 0 1/3 1 1 2/3 0 0 0 The new sample spacing is 2/3 the old sample spacing. The answers are just by interpolating linearly between the samples. Putting it together the result of this step is: (1/3) * 0 0 0 0 0 0 0 1 3 3 2 0 0 1 3 3 2 0 0 0 0 0 0 0 Note that each column is a copy of the original problem, so the column resampling is the same, but with a scale factor for each column. The result is: (1/9) * 0 0 0 0 0 0 0 1 3 3 2 0 0 3 9 9 3 0 0 3 9 9 3 0 0 2 6 6 4 0 0 0 0 0 0 0 1.2 This filter is separable, and it can be written as ([1 2 1]/4) ** ([1 2 1]/4)^T, where ** indicates convolution. Let's call these two filters hf and vf (for horizontal filter and vertical filter). The image is also separable -- it is [1 1] ** [1 1]^T. Let's call these two hi and vi. The result we need to compute, then, is: (hf ** vf) ** (hf ** vf) ** (hi ** vi). The associativity of convolution lets us take away the parentheses and put them back wherever we want, and commutativity lets us reorder the terms. So rewrite this as (hf ** hf ** hi) ** (vf ** vf ** vi) These two grouped terms are the same, and they are 1D convolutions. So we just need to compute [1 2 1] ** [1 2 1] ** [1 1] twice and then form the separable product. [1 2 1] ** [1 2 1]: [1 2 1] [1 2 1] --> 1 [1 2 1] --> 4 (one add) [1 2 1] --> 6 (one multiply, two adds) and by symmetry the result is [1 4 6 4 1]. [1 4 6 4 1] ** [1 1]: [1 4 6 4 1] [1 1] --> 1 [1 1] --> 5 (one add) [1 1] --> 10 (one add) and by symmetry the result is [1 5 10 10 5 1]. Now we convolve that with the vertical version of itself. Doing just one corner: [ 1 5 10 ... ] [ 1] 1 5 10 [ 5] 5 25 50 (two multiplies) [10] 10 50 100 (one new multiply) and the answer by symmetry (with all the 1/4s we left behind) is: (1/256) * 0 0 0 0 0 0 0 0 0 1 5 10 10 5 1 0 0 5 25 50 50 25 5 0 0 10 50 100 100 50 10 0 0 10 50 100 100 50 10 0 0 5 25 50 50 25 5 0 0 1 5 10 10 5 1 0 0 0 0 0 0 0 0 0 By my count this all took 8 nontrivial arithmetic operations, not counting a couple more to compute (1/4)^4 = (1/256) Problem 2: Graphics Pipeline (25 pts) ------------------------------------- 2.1: The clip space coordinates are the eye space ones transformed by the projection matrix. [ 1 0 0 0 ] [ 2/5 7/4 3/5 ] [ 2/5 7/4 3/5 ] [ 0 1 0 0 ] [ 1/5 1/4 3/2 ] = [ 1/5 1/4 3/2 ] [ 0 0 -3/2 -5/2 ] [ -2 -5/2 -3 ] [ 1/2 5/4 2 ] [ 0 0 -1 0 ] [ 1 1 1 ] [ 2 5/2 3 ] <--- w so the columns of that rightmost matrix are the answer pre-perspective. The last row is the w coordinate for perspective correction. The perspective divide results in [ 1/5 7/10 1/5 ] [ 1/10 1/10 1/2 ] [ 1/4 1/2 2/3 ] <--- z' [ 1 1 1 ] In particular, the z' coordinates are in the indicated row. You can verify that applying the viewport matrix results in the coordinates shown in the figure. 2.2 The nine quantities interpolated are beta, gamma, z', n_x, n_y, n_z, u/w, v/w, and 1/w. The first two are the barycentric coordinates; next is the screen-space depth for z-buffering; then the three coordinates of the surface normal; then the two texture coordinates, divided by w for perspective correction; then the inverse of w for perspective correction. 2.3 The values at the vertices are a b c beta 0 1 0 gamma 0 0 1 z' 1/4 1/2 2/3 n_x -0.5 0.5 -0.5 n_y -0.3 -0.3 0.5 n_z 1 1 1 u/w 0 2 1/10 v/w 0 1 3/10 1/w 1/2 2/5 1/3 2.4 At the circled fragment, the interpolated normal is [0 0 1]. We can tell this because the axis aligned right triangle means that beta depends only on x and gamma depens only on y. Since the vertex normals happen to be arranged so that n_x depends only on x and n_y depends only on y, everything is very simple. The circled point is 1/2 way from a's column to b's column, so n_x is 1/2 way between -0.5 and +0.5, which is 0. The circled point is 3/8 of the way from a's row to c's row, so n_y is 3/8 of the way from -0.3 to +0.5, which is also 0. With the normal and the light vector equal, diffuse shading becomes trivial and the result is the same as the diffuse coefficient: (0.5, 0.5, 1). 2.5 In the Gouraud shading case, the three vertices would be shaded first. Since the normals do not face the light exactly, they will have darker colors than the one in the previous part. When the color is interpolated across the triangle it will not get any lighter than the lightest corner, so it will be darker than the Phong shading at the circled pixel (and in fact everywhere but at the corners). Problem 3: Transformations (15 pts) 3.1 This is a rotation by -60 degrees around the axis through (1, 2, 3) in the direction (0, 1, 0). 3.2 This is a scale by 2 along the direction (1, 1, 0). It's a little confusing to get there because the matrices are a bit nonstandard. The outer matrices are 45 degree rotations in x and y combined with scales by sqrt(2). However, these scales can be combined and moved into the center matrix, which then becomes a scale by 2 along the x axis. Problem 4: Splines (25 pts) 4.1 (see separate plots) The cusp happens when both derivatives are zero at the same time -- when that happens the parametric continuity no longer guarantees geometric continuity. 4.2 At the cusp the curve is C^inf and G^0. 4.3 Conveniently enough, beta doesn't affect y(t) and alpha doesn't affect x(t). First use the spline matrix to get the polynomial for x(t) as a function of beta (hereinafter b), by plugging in the x coordinates of the control points: x(t) = [ t^3 t^2 t 1 ] [ -1 3 -3 1 ] [ 1 ] [ 3 -6 3 0 ] [ 1 ] [ -3 3 0 0 ] [ b ] [ 1 0 0 0 ] [ 0 ] = (2 - 3b) t^3 + (-3 + 3b) t^2 + 0 + 0 The derivative of this is is x'(t) = 3 (2 - 3b) t^2 + 2 (-3 + 3b) t Set equal to zero and solve: 0 = 3 (2 - 3b) t^2 + 2 (-3 + 3b) t = (2 - 3b) t^2 + (-2 + 2b) t (factor out 3) = t ((2 - 3b) t + (-2 + 2b)) t = 0 or (2 - 3b) t = 2 - 2b The interesting solution is t_x = (2 - 2b) / (2 - 3b) 4.4 The simple symmetry argument is by reversing the curve and concluding that 1 - t is the same function of alpha that t is of beta: t_y = 1 - (2 - 2a) / (2 - 3a) = -a / (2 - 3a) The possibility for a cusp exists when t_x and t_y coincide: -a 2 - 2b ------ = ------ 2 - 3a 2 - 3b -a (2 - 3b) = (2 - 2b) (2 - 3a) -2a + 3ba = 4 - 4b - 6a + 6ab 4b - 3ba = 4 - 4a b(4 - 3a) = 4 - 4a 4 - 4a b = ------ 4 - 3a and that is the answer. To check: (a) a = 2 => b = (4 - 8) / (4 - 6) = 2 (b) solve for a => a = (4 - 4b) / (4 - 3b) (c) a = 5/2 => b = (4 - 10) / (4 - 15/2) = 12/7, about 1.7 Problem 5: Triangle meshes (15 pts) ----------------------------------- 5.1 It is a square pyramid with an internal triangle separating into two compartments. 5.2 1: delete the internal triangle [0 2 4]; 2: reverse the orientation of the triangle [0 2 3] 5.3 one answer is [4 2 3 0 4 1 2 0] but it seems to work out just fine pretty much no matter where you start building.