CSC418/2504F: Fall 2001 Assignment 3

Nov. 14, 2001. Due: Dec. 5, 2001 in class.

Frequently-asked questions

Solution

  1. Change of Basis [4 marks]
    A segment of a cubic curve B(t) is defined by four control points, all of which are interpolated:
    • B(0)=P1
    • B(1/3)=Q2
    • B(2/3)=Q3
    • B(1)=P4
    Specifying a curve this way is intuitive for a user, but Bézier curves are easier to compute. In this question, you will obtain the Bézier representation of the curve.
    1. [1 mark] Derive the basis matrix M4 for this curve.
    2. [1 mark] Find the tangent vectors T1 and T4 at the endpoints P1 and P4.
    3. [1 mark] Derive the matrix M4H which converts the control points P1, Q2, Q3, P4, to the Hermite control points P1, T1, T4, P4.
    4. [1 mark] Derive the matrix M4B which converts the control points P1, Q2, Q3, P4, to the Bézier control points P1, P2, P3, P4.

  2. Subdivision [4 marks]
    A cubic Bézier curve B(t) can be constructed with the de Casteljau algorithm:
    Q1(t) = lerp(P1,P2,t)
    Q2(t) = lerp(P2,P3,t) R1(t) = lerp(Q1,Q2,t)
    Q3(t) = lerp(P3,P4,t) R2(t) = lerp(Q2,Q3,t) B(t) = lerp(R1,R2,t)
    where lerp(A,B,t)=(1-t)A+tB is simple linear interpolation.
    1. [1 mark] Show that B(t) is tangent to the line through R1 and R2.
    2. [1 mark] A cubic Bézier can be broken up into two halves, B1(t) and B2(t), each of which is a Bézier curve, such that:
      • B1(t)=B(t/2)
      • B2(t)=B(0.5+t/2)

      Find the 7 Bézier control points for B1 and B2.
    3. [1 mark] If we break the two halves into four fourths, we obtain more control points (13 in total). Repeatedly subdividing a Bézier curve yields control points that approximate the curve ever more closely. After n halvings, we will have 2n+1+2n+1 control points. How many arithmetic operations (*,/,+,-) are needed to compute these control points? Assume 2-dimensional points.
    4. [1 mark] Of course, a cubic Bézier curve B(t) can be expressed as a matrix equation:
      • B(t) = T Mb Gb
      • T = [t3 t2 t 1]
      • Gb = [P1 P2 P3 P4]T
      How many arithmetic operations are needed to compute 2n+1+2n+1 points on the curve? Assume 2-dimensional points.

  3. Invariance [2 marks]
    A parametric curve S(t) may written as a weighted sum of control points Pi:

    where fi(t) is a basis function. For a polynomial parametric curve, show that applying an affine transformation to the curve S(t) yields the same result as deforming the control points Pi.

  4. Antialiasing [4 marks]
    You will rasterize the following black polygon on a white background. Black pixels have value 0, and white pixels value 16. For proper anti-aliasing, pixel values should reflect the fraction of their area that is covered by the polygon. Note: the picture below is only a sketch, not a precise drawing.
    • v1=(0,0)
    • v2=(4,0)
    • v3=(5,2)
    • v4=(3,3)
    1. [2 marks] Use pre-filtering to compute the exact coverage for each pixel.
    2. [2 marks] Use 2x2 regular supersampling to approximate the area coverage.
    For both parts, give your answer as a 4x6 grid of pixel values.

  5. Project [25 marks]
    For this part, you have a choice of two possible programming projects. The work must be done in teams of two students. In addition to the code, you should submit a one-page description of your work, detailing the work done by each partner.
    Descriptions:

    1. Ray Tracer: Implement a ray tracer. A good implementation should include the following features:
      • Local Illumination Model for diffuse surfaces.
      • Reflection and refraction for mirror and transparent surfaces.
      • Shadows.
      • Several kinds of primitives:
        • Spheres, Cylinders, Polygons, Cones.
      • Transformed versions of these primitive objects.
      Beware! Ray tracing uses lots of CPU. Keep your recursion depth low (max 2 or 3) and your images tiny (200x200) while testing.

    2. Animation: Implement an interesting animation, using key frames to control the parameters and cardinal splines to interpolate between them. The software will be graded based on two criteria:
      1. Modelling: the difficulty, creativeness and interest of the objects in the scene.
      2. Animation: good handling of object contacts, camera control, and interesting motion (use cubic curves for control, not the linear curves in the skeleton code).
      Beware! Animation can use lots of disk space. Keep your image size small, or you'll likely run out of disk space.

    To submit your work, use one of the following commands: Your submission should include these files:
    1. 'readme.txt', which includes the one-page report, plus any special instructions to the grader.
    2. for the ray-tracer, an image file.
    3. for the animation, an MPEG movie file.
    Sample code: Look here.