Computer Laboratory

Course pages 2014–15

Computer Graphics and Image Processing

Supervision work

The course can be covered comfortably in four supervisions. The schedule below suggests three supervisions following the material as it is taught, followed by a final supervision to go through some Tripos questions, but remember that some past exam questions cover material that is no longer on the syllabus.

The questions were written by Dr Chris Faigle, Prof. James Gain, Dr Jonathon Pfautz, and Prof. Neil Dodgson. Each set of exercises contains up to three sections:

  • Warmup questions -- These are short answer questions that should only take you a few minutes each.
  • Longer questions -- These are geared more towards real exam questions. You should make sure that you can answer these.
  • Advanced questions -- These go beyond the syllabus. They are harder problems that will be worth your while to answer if you find the other questions too easy.

Much of the course concerns design decisions for efficient implementation of graphics algorithms. It would be worth consolidating these through practical programming exercises. Some suggestions are given below, but there is obvious scope for much more extended projects.

Supervisors are advised that setting students all of these exercises is likely to require too much work, and that some exercises should be left for the vacations and revision.

Preparation

Read Chapter 2 of Shirley & Marschner to revise some of the vector mathematics that will be used in the course.

Practical exercise

Refactor the display code that you wrote for the game of Life in last year's Programming in Java course so that it can simulate a raster display with pixels that are big enough to be seen individually and which can show different colours. This will be useful for the ray-tracing and 2D graphics exercises later on.

Introduction and simple rendering

Warmup questions

  1. Suppose you are designing a user interface for someone who is colour blind. Describe how some user interface of your choice should be suitably modified.
  2. Why is it better to look at faint stars and comets slightly off-centre rather than looking directly at them?
  3. In a CAD system using blue lines on a black background would be a poor choice for the interface colours for designing an object. Why is this?
  4. In New Zealand, warning road signs are black on yellow, it being alleged that this is easier to see than black on white. Why might this be true?

Longer questions

  1. Monitor Resolution. Calculate the ultimate monitor resolution (i.e. colour pixels/inch) beyond which better resolution will be unnecessary.
  2. Pixels. Why do we use square pixels? Would hexagonal pixels be better? What about triangles? Do you see any difficulties building graphics hardware with these other two schemes?

Advanced question

  1. Why is the sky blue? [Hints: Why might it be blue? Why are sunsets red? Are the red of a sunset and the blue of the sky related?]

Practical programming

Write a simple ray-tracer. This will involve:

  • designing a class for modelling some geometric primitives such as spheres, cubes and cylinders
  • arranging multiple instances of the primitives to form a scene
  • modelling sources of illumination
  • tracing a ray to find its intersection with the nearest surface
  • tracing rays from the intersection to the sources of illumination
  • (optionally) thinking about reflection, transparency and refraction
  • displaying the results on a grid of pixels

Graphics pipeline, algorithms for 2D and 3D

Warmup questions

  1. Matrices. Give as many reasons as possible why we use matrices to represent transformations. Explain why we use homogeneous co-ordinates.
  2. Texture Mapping. Are there any problems with texture mapping onto a sphere?
  3. Phong. Describe how Phong's specular reflection models real specular reflection. Why is it only a rough approximation? Why is it useful?
  4. Coordinate Systems. Draw pictures to show what is meant by:
    • object coordinates
    • world coordinates
    • viewing coordinates
    • screen coordinates
  5. Triangle mesh approximations. We use a lot of triangles to approximate stuff in computer graphics. Why are they good? Why are they bad? Can you think of any alternatives?

Longer questions

  1. Bézier cubics. Derive the conditions necessary for two Bézier curves to join with
    • just C0-continuity;
    • C1-continuity;
    • C2-continuity.
    What would be difficult about getting three Bézier curves to join in sequence with C2-continuity at the two joins?
  2. Projection. Draw and explain two different scenes which have the same projection as seen by the viewer. What other cues can you give so that the viewer can distinguish the depth information?
  3. Bounding Volumes. For a cylinder of radius 2, with endpoints (1,2,3) and (2,4,5), show how to calculate:
    • an axis-aligned bound box
    • a bounding sphere
  4. BSP Tree. Break down the following (2D!) lines into a BSP-tree, splitting them if necessary:
    • (0,0)-(2,2)
    • (3,4)-(1, 3)
    • (1,0)-(-3,1)
    • (0,3)-(3,3)
    • (2,0)-(2,1)
  5. Sphere Subdividing. We often use triangles to represent a sphere. Describe two methods of generating triangles from a sphere.
  6. Surface detail. Compare and contrast:
    • texture mapping
    • bump mapping
    • displacement mapping
    (You will need to do a bit of background reading.)
  7. 3D Clipping.
    • Compare the two methods of doing 3D clipping in terms of efficiency.
    • How would using bounding volumes improve the efficiency of these methods?
  8. Rotation.
    • Show how to perform 2D rotation around an arbitrary point.
    • Show how to perform 3D rotation around an arbitrary axis parallel to the x-axis.
    • Show how to perform 3D rotation around an arbitrary axis.
  9. 3D Polygon Scan Conversion. Describe a complete algorithm to do 3D polygon scan conversion, including details of clipping, projection, and the underlying 2D polygon scan conversion algorithm.

Advanced Questions

  1. Bézier Patches. Describe how you would form a good approximation to a cylinder from Bézier patches. Draw the patches and their control points and give the co-ordinates of the control points.
  2. Bézier Patches. Given the following sixteen points, calculate the first eight of the next patch joining it as t increases so that the join has continuity C1. Here the points are listed with s=0, t=0 on the bottom left, with s increasing upwards and t increasing to the right:
    (-.2, 3.4, .3)(1, 3.1, -.2)(2, 2.6, -.2)(3.1, 2.8, .2)
    (0, 1.2, .4)(1.2, 2.0, 1.2)(1.4, 1.9, -.2)(2.7, 1.8, .2)
    (.2, 1, -.2)(1.1, .8, .5)(1.4, 1.0, 0)(3.1, 1.1,-.2)
    (0, 0, 0)(1, 0, .5)(2, .2, .4)(2.7, 0,-.2)
  3. Rotations. Define and then compare and contrast the following methods of specifying rotation in 3D. (You will need to look these up.)
    • Quaternions
    • Euler Angles
  4. Improved shading models. Find out about the Cook-Torrance shading model and explain how this improves on the naive diffuse+specular+ambient model.

Practical programming

Write a program using OpenGL to display the scene that you rendered with your ray-tracer. Explore some different surface models in the fragment shader.

Colour, displays and image processing

Warmup questions

  1. Compare and contrast the use of LCDs and electrophoretic displays for screens in portable devices.
  2. Compare the rendering in some different pieces of printed material. Use a magnifying glass to explore the resolution, colours and patterns used.

Longer questions

  1. Colour Spaces. Explain the use of each of the following colour spaces:
    • RGB
    • XYZ
    • HLS
    • Luv
  2. Additive vs Subtractive. Explain the difference between additive colour (RGB) and subtractive colour (CMY). Where is each used and why is it used there?
  3. Error Diffusion. Compare the two methods of Error Diffusion described in the notes, with the aid of a sample image.

Advanced questions

  1. Printing. Select one of
    • laser printing
    • ink jet printing
    • offset printing.
    Find out how it works and write a 1000 word description which a 12 year old could understand.
  2. Displays. Select one of
    • electrophoretic display
    • DMD display
    • LCD display.
    Find out how it works and write a 1000 word description which a 12 year old could understand.

Practical programming

Implement some of the line and curve drawing and clipping algorithms in 2D.