Course pages 2013–14

Computer Graphics and Image Processing

Supervision work

The lecturers recommend that supervisors set work following this pattern. Supervisors are advised that setting students all of the exercises is likely to be too high a workload and that some exercises should be left for the student to do as revision before exams.

Supervision 1: Complete several of the practical programming exercises on 2D computer graphics. Your supervisor should choose an appropriate subset.

Supervision 2: Complete more of the practical programming exercises, on 2D and 3D, as set by your supervisor. Attempt one past exam question on 2D computer graphics and some other exercises, as set by your supervisor.

Supervision 3: Complete a final group of practical programming exercises, on 3D computer graphics, as set by your supervisor. Attempt at least one past exam question on 3D computer graphics and some other exercises, as set by your supervisor.

Supervision 4: Attempt three complete past exam questions, as set by your supervisor.

Below you will find both practical exercises and written exercises.

Practical exercises

We provide a Java resource (JAR) file that allows you to concentrate on implementing the algorithms rather than on getting the environment working. The JAR file can be downloaded from the programming environment tab.

Textbook references

Textbook references are provided for those who want to read more about the various parts of the course. It is not essential to understand everything in the referenced sections. References are to:
FvDFH: Foley, J.D., van Dam, A., Feiner, S.K. & Hughes, J.F., Computer Graphics: Principles and Pratice, second edition, Addison-Wesley, 1990.
SSC: Slater, M., Steed, A. & Chrysanthou, Y., Computer graphics and virtual environments: from realism to real-time, Addison-Wesley, 2002.

2D computer graphics

The 2D algorithms

This part of the course demonstrates the implementation and optimisation of some of the most basic graphics algorithms. Graphics cards implement many of these algorithms, using them millions of times a second, so optimisation is critical. There are several dependencies between the algorithms that are taught:

• Polygon clipping and line clipping both need the intersection of two lines.
• Bezier curve drawing and Douglas-Peuker line chain simplification both need the distance of a point to a line and a line drawing algorithm.
• Circle drawing and polygon filling both have parts based on the line drawing algorithm

Line drawing algorithms

Textbook references: FvDFH sec. 3.2 (pp.72-81), SSC sec. 17.3 (pp.366-370)

Practical exercise 1-1: Download the files easel.jar and LineDrawer.java, create a Java project in your favourite environment (Eclipse works well), compile and run it. The implements Bresenham's line drawing algorithm, for floating-point endpoints, in the first octant. It draws a set of lines in that octant. Notice that the computer graphics coordinate system has the positive y-axis pointing downwards, contrary to all of the diagrams in the notes and contrary to normal mathematical usage.

Practical exercise 1-2: Using LineDrawer.java as a model, create a new java project in which you implement the Midpoint line drawing algorithm in the first octant, for floating-point end points. This should simply require you to replace Bresenham's algorithm with the Midpoint algorithm given in the lecture slides.

Practical exercise 1-3: Add code to your Midpoint line drawing algorithm to draw a line in any of the eight octants. Test it. Notice that LineDrawer.java already has code to swap the two endpoints (octant 5 goes to octant 1, etc.) so that it need consider cases in only four of the eight octants.

Circle and ellipse algorithms

Textbook references: FvDFH sec. 3.3 (pp.81-91)

Practical exercise 1-4: Implement the Midpoint circle drawing algorithm for integer radius and integer centre location. Hints: (i) implement the algorithm for one octant, centred on the origin, then draw the other octants by manipulating the co-ordinates of the drawn point: (x,y), (-x,y), (y,x), (y,-x), etc. (ii) implement the algorithm for a circle centred on the origin and then simply offset the pixel that is drawn by the coordinates of the actual centre.

Cubic curve algorithms

Textbook references: FvDFH sec. 11.2.1 & 11.2.2 (pp.478-491), SSC sec. 19.4 (pp.394-397)

Practical exercise 2-1: Write the Bézier adaptive algorithm, using your Midpoint line drawing to draw the lines. To test this on a pixel grid of size H?W, try the Bézier curve specified by the four points: (1,1), (2H,1), (-H,W-1), (H-1,W-1). Draw the same Bézier curve at five different tolerances: 33, 10, 3.3, 1, 0.33 pixels.

Help: if you have been unable to get the midpoint line drawing algorithm working, then download this working version from the course website.

Line chain simplification

Optional practical exercise 2-2: Write the Douglas-Peuker line chain simplification algorithm. This will use some of the same code as the Bézier adaptive algorithm (distance of a point to a line segment). You will need a data structure that can contain a list or array of vertices.

Clipping lines

Textbook references: FvDFH sec. 3.12(pp.111-117), SSC sec. 17.2 (pp.355-365)

Practical exercise 3: Write the Cohen-Sutherland clipping algorithm that clips a line against a rectangular axis-aligned box.

Hints:
To test this visually: choose a clipping box that is well inside the canvas that you are using, draw the clipping box, select a range of unclipped lines that fall on the canvas and that test as many cases as you can think of, draw the unclipped lines, then draw the clipped lines in a different colour. The Boolean variables can be implemented using integers. For example:
int q = 0 ;
if( x < xl ) q |= 1;
if( x > xr ) q |= 2;
...
Beware of Java's precedence when performing Boolean operations and comparisons on integers. For example, you need to use parentheses in these conditions:
if( (q0&q1) > 0 ) {...
if( (q0|q1) == 0 ) {...

Filling polygons

Textbook references: FvDFH sec. 3.6 (pp.92-99), SSC sec. 12 (pp.260-266)

Practical exercise 4-1: Write a polygon fill algorithm.

Hints: This is considerably more challenging that the previous practical exercises. You need to establish good data structures for vertices, edges, and the information required by the active edge list. You need to manage either lists or arrays of edges, and you need to be able to sort these arrays into order both on lowest y value and current x intersection value. Use Java's inbuilt mechanisms to handle the arrays and the sorting.

Clipping polygons

Textbook references: FvDFH sec. 3.14 (pp.124-127), SSC sec. 10.2 (pp.230-232)

Optional practical exercise 4-2: Write the Sutherland-Hodgman polygon clipping algorithm.

Hints: you will need the data structures that you used for the polygon fill algorithm. Try clipping one polygon against another, ensuring that the clip polygon is convex).

3D computer graphics

Practical exercise 5-1: Download the file Shapes3D.java. This compiles to display a coloured cube, scaled non-uniformly, and rotating around an origin. There are three transforms in the program: a non-uniform scaling, a rotation, and a translation. Compile and run the program six times for the six possible orderings of scaling, rotation and translation. Observe what happens. From this evidence, deduce the order in which the operations are applied by Open GL to the drawn object.

Practical exercise 5-2: You can use gl.glPushMatrix() and gl.glPopMatrix() to save and restore the current tranformation matrix. Use this, along with the code from Exercise 5-1, to display the multiple different versions of the cube, transformed in different ways, all at the same time.

Practical exercise 6 (was exercise 7): Develop pseudocode for algorithms that shade a triangle according to:
(a) Gouraud shading.
(b) Phong shading.
You can use the scan line polygon fill algorithm (Exercise 4-1) as a starting point.

Written Exercises

These questions were created by Dr Chris Faigle, Prof. James Gain, Dr Jonathon Pfautz, and Prof. Neil Dodgson. There are four sets of exercises, one for each of the four parts of the course. 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.

You should also attempt some past exam questions. Remember that some past exam questions cover material that is not on this year's syllabus.

1. Background material

1.1 Warmup questions

1.1.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.

1.1.2. Why is it better to look at faint stars and comets slightly off-centre rather than looking directly at them?

1.1.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?

1.1.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?

1.2 Longer questions

1.2.1. Colour Spaces. Explain the use of each of the following colour spaces: (a) RGB; (b) XYZ; (c) HLS; (d) Luv

1.2.2. Monitor Resolution. Calculate the ultimate monitor resolution (i.e. colour pixels/inch) at which point better resolution will be indistinguishable.

1.2.3. 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?

1.2.4. Additive vs Subtractive. Explain the difference between additive colour (RGB) and subtractive colour (CMY). Where is each used and why is it used there?

1.3 Advanced questions

1.3.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?]

1.3.2. Printing. Select one of (a) laser printing, (b) ink jet printing, (c) offset printing. Find out how it works and write a 1000 word description which a 12 year old could understand.

1.3.3. Displays. Select one of (a) electrophoretic display, (b) DMD display, (c) LCD display. Find out how it works and write a 1000 word description which a 12 year old could understand.

2. 2D Computer Graphics

2.1 Warmup Questions

2.1.1. Matrices. Give as many reasons as possible why we use matrices to represent transformations. Explain why we use homogeneous co-ordinates.

2.1.2. BitBlt. What factors do you think affect the efficiency of BitBlt's ability to move images quickly?

2.2 Longer Questions

2.2.1. Bézier cubics. Derive the conditions necessary for two Bézier curves to join with (a) just C0-continuity; (b) C1-continuity; (c) C2-continuity. What would be difficult about getting three Bézier curves to join in sequence with C2-continuity at the two joins?

3. 3D Computer Graphics

3.1 Warmup questions

3.1.1. Texture Mapping. Are there any problems with texture mapping onto a sphere?

3.1.2. Phong. Describe how Phong's specular reflection models real specular reflection. Why is it only a rough approximation? Why is it useful?

3.1.3. Coordinate Systems. Draw pictures to show what is meant by:
object coordinates,
world coordinates,
viewing coordinates,
screen coordinates.

3.1.4. 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?

3.2 Longer questions

3.2.1. 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.2.2. Bounding Volumes. For a cylinder of radius 2, with endpoints (1,2,3) and (2,4,5), show how to calculate: (a) an axis-aligned bound box, (b) a bounding sphere.

3.2.3. 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) and (2, 0) (2, 1)

3.2.4. Sphere Subdividing. We often use triangles to represent a sphere. Describe two methods of generating triangles from a sphere.

3.2.5. Compare and Contrast. Compare and contrast: texture mapping, bump mapping and displacement mapping (you will need to do a bit of background reading).

3.2.6. 3D Clipping. (a) Compare the two methods of doing 3D clipping in terms of efficiency. (b) How would using bounding volumes improve the efficiency of these methods?

3.2.7. 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.

3.2.8. 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.

3.3 Advanced Questions

3.3.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.

3.3.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.

3.3.3. Rotations. Define and then compare and contrast the following methods of specifying rotation in 3D. [you will need to look these up]
(a) Quaternions
(b) Euler Angles

3.3.4. Improved shading models. Find out about the Cook-Torrance shading model and explain how this improves on the naive diffuse+specular+ambient model (slide 247).

4. Image Processing

4.2. Longer questions

4.2.1. Error Diffusion. Compare the two methods of Error Diffusion described in the notes, with the aid of a sample image.