CS 4390
Computer Graphics

Fall 1998
College of Computing 201
MWF 11:00-12:00

Homework Solutions

Here's a pointer back to the homework.

Illumination

  1. Explain the differences between ambient, diffuse, and specular reflection.

    Ambient reflection is designed to capture the effect of a certain amount of light hitting the object from all directions equally (for example, after the light has bounced off many surfaces). It is constant over an object surface, and does not vary with surface normal or viewpoint.

    Diffuse reflection captures the effect of the energy from a point or directional light being reflected back from the surface equally in all directions. A rough surface would scatter light in this way. Diffuse reflection differs from ambient reflection because its intensity depends on the relative directions of the light and the surface normal. A diffuse reflection has greater intensity on parts of the surface where the surface normal points more toward the light.

    Specular reflection captures the highlights we see from reflections of light on smooth surfaces. It captures the effect that light bouncing off a smooth surface will be primarily reflected about the surface normal. In the limit, we have a perfect mirror, and light is *only* reflected in this direction. Specular reflection differs from ambient and diffuse reflection because it depends on the location of the viewer, as well as on the surface normal and light source vectors.

  2. This question contains enough information to describe a very simple scene containing two lights and a single triangle. From this scene, using the Phong illumination model, you can determine exactly how to shade this triangle.

    You are given a triangle with endpoints:

    P1 = [1 1 1 1]T
    P2 = [0 2 1 1]T
    P3 = [0 0 1 1]T

    This triangle is a fully saturated red (Od,R = 1), and the specular color is white. The triangle has the following material properties:

    ka = 0.7
    kd = 0.9
    ks = 0.6
    n = 10 (n is the specular reflection exponent)

    You have the following light sources:

    A white ambient light with intensity 0.1.
    A white point light located at [1 1 5 1]T with intensity 0.5.

    The viewer is at point [1 2 5 1]T

    (A) Compute the intensity of the ambient reflection at the interior point [0.5 1 1 1]T.

    Use IakaOd

    RED: 0.1(0.7)(1) = 0.07
    GRN: 0.1(0.7)(0) = 0.00
    BLU: 0.1(0.7)(0) = 0.00

    (B) Compute the intensity of the diffuse reflection at the same point.

    Use IpkdOd(nHat . LHat)

    For this triangle, normal nHat = [0 0 1 0]T

    Light vector L = (light_position - sample_position) = [1 1 5 1]T - [0.5 1 1 1]T = [0.5 0 4 0]T
    Normalizing, LHat = [0.124 0 0.992 0]T

    Taking the dot product: (nHat . LHat) = 0.992

    RED: 0.5(0.9)(1)(0.992) = 0.446
    GRN: 0.5(0.9)(0)(0.992) = 0.000
    BLU: 0.5(0.9)(0)(0.992) = 0.000

    (C) Compute the intensity of the specular reflection at this point.

    Use IpksOs(rHat . VHat)n

    From the construction below, rHat = 2(LHat . nHat)nHat - LHat

    In this case, rHat = [-0.124 0 0.992 0]T

    Viewer vector V = (viewer_position - sample_position) = [1 2 5 1]T - [0.5 1 1 1]T = [0.5 1 4 0]T
    Normalizing, VHat = [0.120 0.241 0.963 0]T

    Taking the dot product: (rHat . VHat) = 0.940
    To the nth power: 0.94010 = 0.539

    RED: 0.5(0.6)(1)(0.539) = 0.162
    GRN: 0.5(0.6)(1)(0.539) = 0.162
    BLU: 0.5(0.6)(1)(0.539) = 0.162

    (D) Given this intensity information, what color should a pixel at this point be drawn?

    Sum the ambient, diffuse, and specular terms:

    RED: 0.07 + 0.446 + 0.162 = 0.678
    GRN: 0.00 + 0.000 + 0.162 = 0.162
    BLU: 0.07 + 0.000 + 0.162 = 0.162

    Color = (0.678, 0.162, 0.162)

    (E) Describe the contribution of the two different light sources.

    The ambient light contributes a small amount of red at this point. Most of the color comes from the point light source.

Shading

  1. What is flat shading?

    Flat shading means to choose a single color for each polygon in an image.

  2. When would you choose Phong shading over Gouraud shading?

    Phong shading does a better job than Gouraud shading of capturing specular highlights, especially when the specular highlights vary substantially over single polygons. Phong shading would be a good choice if the necessary computational time is available and sharp specular highlights are needed.

  3. This question builds on your answers from the question #2 in the illumination homework above. Assume that the triangle described there is really an approximation to a curved surface. We could shade the triangle using flat shading, choosing for example, the color computed in part D of question #2 above.

    An alternative would be to use one of the smooth shading techniques. Assume that good estimates for outward pointing unit normal vectors at the vertices P1, P2, and P3 are as follows:

    normP1 = [ 0.30, 0.00, 0.95, 0]T
    normP2 = [ 0.00, 0.50, 0.87, 0]T
    normP3 = [-0.10, -0.10, 0.99, 0]T

    (A) Compute the new color values at each of the three vertices.

    Compute the vectors at point 1:

    nHat = [0.30, 0.00, 0.95, 0]T (the normal is given)
    LHat = [0.00, 0.00, 1.00, 0]T (the light is above point 1)
    rHat = [0.57, 0.00, 0.81, 0]T (from LHat and nHat as described above)
    vHat = [0.00, 0.24, 0.97, 0]T (viewer_position - point1)

    From these vectors:

    Ambient: (0.07, 0.00, 0.00)
    Diffuse: (0.428, 0.00, 0.00)
    Specular: (0.029, 0.029, 0.029)

    Summing, the COLOR at point1 = (0.527, 0.029, 0.029)

    Compute the vectors at point 2:

    nHat = [0.00, 0.50, 0.87, 0]T (the normal is given)
    LHat = [0.236, -.236, 0.943, 0]T (light_position - point2)
    rHat = [-.236, 0.938, 0.279, 0]T (from LHat and nHat as described above)
    vHat = [0.24, 0.00, 0.97, 0]T (viewer_position - point2)

    From these vectors:

    Ambient: (0.07, 0.00, 0.00)
    Diffuse: (0.316, 0.00, 0.00)
    Specular: (0.00, 0.00, 0.00)

    Summing, the COLOR at point2 = (0.386, 0, 0)

    Compute the vectors at point 3:

    nHat = [-.10, -.10, 0.90, 0]T (the normal is given)
    LHat = [0.236, .236, 0.943, 0]T (light_position - point3)
    rHat = [-.413, -.413, 0.811, 0]T (from LHat and nHat as described above)
    vHat = [0.218, 0.436, 0.873, 0]T (viewer_position - point3)

    From these vectors:

    Ambient: (0.07, 0.00, 0.00)
    Diffuse: (0.399, 0.00, 0.00)
    Specular: (0.00, 0.00, 0.00)

    Summing, the COLOR at point3 = (0.469, 0, 0)

    (B) Use Gouraud shading to compute the color of the point [0.5 1 1 1]T. Assume that the triangle projects onto the display without distortion, so that linear interpolation along the triangle surface gives the same results as linear interpolation in the space of the display.

    Referring to the diagram below:

    ColorOf(A) = 0.5(ColorOf(P3) + ColorOf(P2)) = (0.428, 0, 0)
    ColorOf(P) = 0.5(ColorOf(A) + ColorOf(P1)) = (0.478, 0.015, 0.015)

    (C) Use Phong shading to compute the color of the point [0.5 1 1 1]T.

    Interpolate normals:

    nA = 0.5(nHatP3 + nHatP2) = [-0.05 0.2 0.91 0]T
    Normalizing, nHatA = [-0.05 0.21 0.98 0]T
    nP = 0.5(nHatA + nHatP1) = [0.125 0.105 0.965 0]T
    Normalizing, nHatp = [.128 0.107 0.986 0]T

    From the previous calculation of color at this point, we can get vectors LHat and VHat. From LHat and nHat, we calculate a new rHat:

    LHat = [0.124 0 0.992 0]T
    VHat = [0.120 0.241 0.963 0]T
    rHat = [0.131 0.213 0.968 0]T

    From these vectors:

    Ambient: (0.07, 0.00, 0.00)
    Diffuse: (0.447, 0.00, 0.00)
    Specular: (0.30, 0.30, 0.30)

    Summing, the COLOR at point p = (0.817, 0.30, 030)

    (D) How do the diffuse and specular components of intensity differ for flat shading, Gouraud shading, and Phong shading?

    Looking at just the red color component:

    Flat shading: Diffuse = 0.446, Specular = 0.162
    Gouraud shading: Diffuse = 0.463, Specular = 0.015
    Phong shading: Diffuse = 0.447, Specular = 0.300

    The diffuse component comes out very close in all three cases. For this polygon, linear interpolation of either colors or normals will produce a reasonable value for the diffuse component.

    The estimate of the specular component varies a great deal, however. In this case, linear interpolation of colors provides an especially poor approximation to the specular color component.

    (E) Compare the amount of computation required for each type of shading.

    The difference in computation required is dramatic. For this case, assuming that color has already been computed for the three vertices:

    Gouraud shading:

    Linear interpolation (averaging) for two color vectors.

    Phong shading:

    Linear interpolation plus normalization for two vectors to get the normal.
    One scale, one dot product, and one subtraction to get rHat.
    One dot product plus a few multiplies to get the diffuse component.
    One dot product to the power of 10 plus a few multiplies to get the specular component.
    Addition of reflection components to get the color.

    Curves

    1. (A)What does it mean for a curve to be C2 continuous?

      A curve Q(t) is C2 continuous if the curve itself is continuous, and its first and second derivatives with respect to t are also continuous.

      (B)Suppose that we want to draw a C2 continuous curve to connect points A and B shown below:

      We know that the endpoints of the curve we wish to draw are A and B. Suppose that we also know all of the derivatives of the curve at those endpoints. In general, can we produce a C2 continuous splice between A and B with a cubic polynomial curve? Why or why not?

      We cannot, in general, produce a C2 continuous splice between A and B using a cubic polynomial curve, because we do not have enough free parameters to meet all of the constraints. If we consider only the x component of the curve over time, x(t), then

      x(t) = at3 + bt2 + ct + d

      We have four unknowns a,b,c, and d. We have 6 constraint equations, however, because we need to match x, x', and x'' to the existing curve segments at both points A and B in order to create a C2 continuous curve. (Parameters x' and x'' are the first and second derivatives of the curve with respect to t).

      (C)What type of curve would you choose to draw a C1 continuous splice between A and B? Give the value of the geometry vector for this curve.

      2. Since we know the endpoints and the derivatives of the curve at points A and B, a good choice would be a hermite spline. The geometry vector for the hermite spline would be

      [A B A' B']T
      where A' is the tangent to the existing curve at point A, and B' is the tangent to the existing curve at point B.

    2. In class we saw that the tangent vectors used for the Hermite curve could be related to the control points of the Bezier curve using the equations:
      R1 = 3(P2 - P1)
      R2 = 3(P4 - P3)

      Suppose that these equations were of the form:

      R1 = b(P2 - P1)
      R2 = b(P4 - P3)

      For some unknown value b. Now, consider the four equally spaced Bezier points (forming a line segment along the x-axis):

      P1 = (0, 0, 0)
      P2 = (1, 0, 0)
      P3 = (2, 0, 0)
      P4 = (3, 0, 0)

      Show that, for parametric curve Q(t) to have constant velocity from P1 to P4, b must equal 3.

      Consider the x(t) component only. Use the equation x(t) = TMHGH, x. Taking the derivative with respect to t, we have

      x'(t) = T'MHGH, x
      x'(t) = [3t2 2t 1 0]MHGH, x

      Looking up MH in the text and multiplying with T':

      x'(t) = [m1 m2 m3 m4]GH, x
      m1 = 6t2-6t
      m2 = -6t2+6t
      m3 = 3t2-4t+1
      m4 = 3t2-2t

      In this case, we have endpoints at x=0 and x=3, and the tangent vectors are both b, so the geometry vector is:

      GH, x = [0 3 b b]T

      Multiplying and collecting terms:

      x'(t) = b + t(18-6b) + t2(-18+6b)

      For constant velocity, the t and t2 terms above must be zero. This means that b must be 3.

    Curves2

    1. Why will it be difficult to use a nonrational, uniform B-spline curve to connect A and B?

      This would require some amount of extra computation because the geometry vector of the B-spline curve does not express endpoints of the spline directly. (The endpoints of the spline are not control points of the curve.) A better choice might be a Hermite or Bezier curve.

    2. For nonrational, uniform B-Splines, we have the expression Qi(t) = TMBsGBs, i, with vectors T, MBs, and GBs, i defined as follows:

      Use this expression for Qi(t) to show that two adjacent curves i and i+1 have C2 continuity at the join point.

      3. To show that the curve has C2 continuity at the join point, we need to check that the curve and its first and second derivatives are continuous at the join point. In other words:

      Qi(1) = Qi+1(0)
      Qi'(1) = Qi+1'(0)
      Qi''(1) = Qi+1''(0)

      where Qi'(t) is the first derivative of Q with respect to t, and Qi''(t) is the second derivative of Q with respect to t.

      This example walks through the third of these tests. The other two can be done in a similar fashion.

      Curve i has the geometry vector GBs, i = [Pi-3 Pi-2 Pi-1 Pi]T

      Curve i+1 has the geometry vector GBs, i+1 = [Pi-2 Pi-1 Pi Pi+1]T

      To test whether the second derivative is continuous at the join point, we test whether:

      Qi''(1) = Qi+1''(0)

      Qi''(t) = T''MBsGBs, i

      Evaluating T'':
      Qi''(t) = [6t 2 0 0] MBsGBs, i

      Multiplying T'' by MBs:
      Qi''(t) = 1/6[(-6t+6) (18t-12) (-18t+6) (6t)]GBs, i

      Simplifying:
      Qi''(t) = [(-t+1) (3t-2) (-3t+1) (t)]GBs, i

      Evaluate the second derivative at the end of the first curve:
      Qi''(1) = [0 1 -2 1]GBs, i = Pi-2 - 2Pi-1 + Pi

      Evaluate the second derivative at the beginning of the second curve:
      Qi+1''(0) = [1 -2 1 0]GBs, i+1 = Pi-2 - 2Pi-1 + Pi

      Since Qi''(1) = Qi+1''(0), the second derivative of the curve is continuous at the join point.

    3. Suppose we want to construct a parametric, bicubic surface that is a flat, square patch with corners at the following four (x, y, z) locations:
      (0, 0, 0)
      (1, 0, 0)
      (0, 1, 0)
      (1, 1, 0)

      (A)Derive the geometry vector to construct this patch as a Hermite surface patch. Align parameter s with the x-axis and parameter t with the y-axis.

      For a Hermite surface patch, we have:

      Q(s, t) = SMHGH(t)
      GH(t) = [P1(t) P4(t) R1(t) R4(t)]T

      In this case:

      P1(t) = (0, 0, 0) + t(0 1 0)
      P4(t) = (1, 0, 0) + t(0 1 0)
      R1(t) = (1, 0, 0)
      R4(t) = (1, 0, 0)

      The geometry vector is:

      (B)What is the geometry vector if we make this a Bezier surface patch?

      For a Bezier surface patch, we have:

      Q(s, t) = SMBGB(t)
      GB(t) = [P1(t) P2(t) P3(t) P4(t)]T

      In this case:

      P1(t) = (0, 0, 0) + t(0 1 0)
      P2(t) = (1, 0, 0) + t(0 1 0)
      P3(t) = (0, 0, 0) + t(0 1 0)
      P4(t) = (1, 0, 0) + t(0 1 0)

      The geometry vector is:

    Object Modeling

    1. What is an octree representation? How does it compare to using a spatial occupancy grid to model an object?

      An octree data structure can be used to represent the portions of 3D space occupied by an object. It can be constructed in a top-down fashion, starting with a set containing a single cell enclosing the entire object. Cells in the set are recursively subdivided into 8 parts. Subdivision stops when one of the follow is true:

      a cell is completely full,
      a cell is completely empty,
      the maximum level of subdivision has been reached.

      An octree representation differs from a spatial occupancy grid because it provides a mechanism for grouping cells, rather than representing all cells at the maximum level of subdivision. In general, the number of cells in an octree will vary with the surface area of an object rather than with its volume.

    2. One advantage to an octree or quadtree representation over a surface representation of an object is that constructive solid geometry operations are relatively straightforward and fast to compute.

      (A)Describe an algorithm for doing the union operation for two quadtrees. Be careful to compress nodes when possible to maintain a compact representation of the object.

      Trace through the two trees in parallel, depth-first, starting at their roots. Take the following actions based on the values found in the two trees:

      If we have one of (FF, EF, FE, PF, FP)

      add F to the new tree

      If we have (EE)

      add E to the new tree

      If we have (PP)

      add P to the new tree
      add children to queue

      If we have (EP)

      add P to the new tree
      subdivide E as having 4 "E" children
      add children to queue

      In a second pass, once the tree is constructed, trace through the new tree depth-first, grouping any P node with 4 F children into an F node, and any P node with 4 E children into an E node.

      (B)Trace the operation of the union algorithm on the two quadtrees below. Draw a sketch of the two objects and their union to test your algorithm.


      Sketch:

    3. In class, we defined a simple grammar and saw that the following rewrite rule could be traced through several generations to produce the structure in the images shown.
      Start = F
      F -> F[+F]F[-F]F

      Trace the first few generations of branching structures using the following rewrite rule:

      Start = F
      F -> F[+F][-F[-F][+F]]FF