# Exercises for the first supervision

These exercises are drawn from past exam questions.

• [2.3/4] (a) Describe the situations in which it is sensible to use a winged-edged data structure to represent a polygon mesh and, conversely and, conversely, the situations in which a winged-edged data structure is not a sensible option for representing a polygon mesh. (b) What is the minimum information which is required to successfully draw a polygon mesh using Gouraud shading? (you may need to refer to the Part IB course to refresh your memory about what is required for Gouraud shading).
• [3.7/11] (i) Show how to find the first intersection between a ray and a finite-length, open-ended cone, centred at the origin, aligned along the x-axis, for which both ends of the finite-length are on the positive x-axis (i.e. 0 < xmin < xmax).
(ii) Extend this to cope with a closed cone (i.e. the same cone, but with end caps). Take care to consider any special cases.
(iii) Extend this further to give the normal vector at the intersection point.
• [3.7/12] (a) A disc is a finite, planar, circular object. Describe an algorithm to find the point of intersection of an arbitrary ray with an arbitrary disc in three dimensions. Ensure that you describe the parameters used to define both the ray and the disc.
(b) Given the above algorithm and an algorithm to find the intersection of an arbitrary ray with a finite-length open cylinder, a programmer has two choices for implementing an algorithm to find the intersection with a finite-length closed cylinder. She could simply use the finite-length open cylinder primitive and two disc primitives. Alternatively she could implement the finite-length closed cylinder as a primitive in its own right by adding extra code to the open cylinder algorithm. Compare the two alternatives in terms of effciency and accuracy.
• [2003 P9 Q6 (c)] Show how the following object can be constructed using Constructive Solid Geometry (CSG). You may assume the following primitives: sphere, cylinder, cone, torus, box. [You are expected to describe which primitives are needed and how they are combined but you are not expected to specify accurately all of the parameters of the primitives.]
• [8.8.2/3] List the three ways of combining objects using constructive solid geometry (CSG). Describe how an object built using CSG can be represented using a binary tree. Given the intersection points of a ray with each primitive in the tree, explain how these points are passed up the tree by each type of combination node to produce a list of intersection points for the whole CSG object.
• [1999 P9 Q4 (d)] Explain form factors and view factors in radiosity. Outline an implementable method of calculating view factors. Describe how your method might leverage existing hardware acceleration.
• Explain photon mapping, highlighting the two portions of the algorithm which show Monte Carlo integration.
• The one-ring of a vertex is the (usually ordered) set of vertices which lie exactly one edge away from a given vertex on a polyhedral surface. Given a vertex V with one-ring {v0,...,vn-1}, give a formula for the discrete curvature of the surface at V.

 © 2009 Neil Dodgson, Alex Benton Please send any comments to Alex Benton (A.Benton@damtp.cam.ac.uk) Page last updated on 25-Feb-2009 at 13:12 by Alex Benton