Exam Preparation Deck

Question 1

What is radiosity method? How does it work?

Answer 1

• Illumination method which simulates global dispersion and reflection of diffuse light only.
• Scene divided into polygons, where each polygon has three associated values: emittance, radiosity and reflectance.
• Between two polygons, we can also compute form factor - the portion of light hitting other.
• After solving equation, we find vertex illumination from patch illuminations.
• Shade by Gourad.

Question 2

How do you compute form factor?

Answer 2

Visibility V(i,j) is often defined by hemicube methods:

• Encase patch centre with a hemicube.
• Render the scene from point of view of patch, through the walls of cube.
• V(i,j) = percentage of patch j seen on the hemicube.

Question 3

What is an implicit surface?

What is its advantages/disadvantages?

Answer 3

• Define a force function f(P) over complete 3D space.
• Surface is where f(P) = c, a constant.
• f(P) often constructed by summing points of contribution f_i(P), where each f_i can be any function in space.
• Typically f_i(P) = g(|P-C_i|) for some function g.
• Very hard to specify engineering surface.
• Must use marching cubes then polygon-scan conversion.

Question 4

What is NURBS?

What advantages/disadvantages do it bring?

Answer 4

• Define a patch based on control points and basis functions.
• Rectangular grid of control points, with two knot vectors: one for each direction (bivariate).
• Can be easily subdivided into polygons. Or you can use numerical methods to raytrace.
• Can define almost any surface.
• But hard to ensure C2 continuity when joining patches.

Question 5

What is constructive solid geometry?

What are its advantages/disadvantages?

Answer 5

• Boolean operations on real space.
• Defined on primitive objects - sphere, cubes… in fact anything that can partition space into half.
• Operation includes union, intersection and difference.
• Sadly, could only be ray-traced.
• Can handle surfaces not possible with NURBS, but dependent on avaiable primitives.

Question 6

Define Doo-Sabin method.

Which of the following vanishes after one iteration?

• Extraordinary faces
• Extraordinary vertices

Answer 6

• Subdivides on quadrilateral mesh only.
• Perform face centered subdivision.
• A 3D extension to Chaikin: [1,3,3,1]^2.
• Extraordinary vertices vanish after one step.

Question 7

Define Catmull-Clark method.

Which ones vanish after one iteration?

• Extraordinary faces.
• Extraordinary vertices.

Answer 7

• Works on quadrilateral mesh only.
• Perform vertex centered subdivision.
• Extension to the 2D kernel: [1,4,6,4,1]^2.
• Extraordinary faces vanish after one iteration.

Question 8

How to test if a vertex V is strictly inside a convex polygon P?

Answer 8

Question 9

Define Gaussian curvature of a point.

Answer 9

• Gaussian curvature of a region is the area of surface on unit sphere swept by surface normals of the region, divided by the area of region itself.
• Gaussian curvature of a point is the limit of this ratio, as the area of the region tends to zero.

Question 10

State the Poincare formula…

It relates vertex/edge/face counts, genus, and Euler Characteristics.

Answer 10

Question 11

State relation between summed angle deficits and Euler characteristic.

Answer 11

Question 12

What is a Voronoi diagram for a set of points?

Answer 12

• It divides space into a set of cells C_i.
• Each cell C_i contains all points in space that’s closer to P_i than any other P_j.

Question 13

What is the Delaunay triangulation?

Answer 13

• The dual of Voronoi Diagram.
• A graph in which every edge connects adjacent cells of (P_i, P_j) in the Voronoi Diagram.

Question 14

Define equiangularity of a triangulation.

Answer 14

• The sorted list of angles (\alpha_1 to \alpha_{3t}) of the triangles.

Question 15

What does it mean for Voronoi Diagram having the empty circle property?

Answer 15

No point in set will lie inside the circle circumscribing any three points sharing a triangle in the Voronoi diagram.

Question 16

Describe the scattering phase of photon mapping.

Answer 16

• Photons are fired from each light source, scattered in random directions.
• Number of photons per light depends on surface area and brightness.
• Photons are fired through the scene by standard raytracing. When they strike a surface, either absorbed, reflected or refracted (depends on prob dist).
• Whenever photons are absorbed, cache location, direction and energy of photon.
• Use kd-tree to support fast insertion and lookup.

Question 17

Describe photon mapping’s rendering phase.

Answer 17

• Raytrace scene from point of view of camera.
• At each first contact point P, use raytracer for specular illumination.
• Compute diffuse illumination from photon map.
• Done by summing contrib of photons along eye ray, within a sphere of fixed size.
• No ambient.
• Calculate caustics directly from the photon map. Usually use caustic map (another photon map) for speed.

Question 18

What is a vertex shader?

What can you do with it?

Answer 18

• It runs once for every triangle vertex passed to the graphics card.
• Produces a position, a color, and optional custom variables.
• Wide range of geometric and color operations supported. Includes vertex/normal transformation, texture coordinate generation/transformation, lighting…

Question 19

What is a fragment shader?

How does it work?

Answer 19

• It runs once for every fragment, i.e. every time when a color is rendered into a pixel.
• Produces fragment color and depth.
• Wide range of color and texture operations supported: Texture access/application, color summation…

Question 20

Explain the kd-tree structure.

How does it aid ray-tracing?

Answer 20

• KD-Trees splits space into zones based on axis-aligned binary splits.
• O(nlgn) insertion time, O(n^{2/3}) search time.
• Acceleration of raytracing possible by identifying zones that the ray passes.
• Ray only have to be checked against objects within such zones.

Question 21

Why are normals to discrete surfaces (at vertex) always approximations?

Give the best formula provided in lectures.

Answer 21

A discrete surface is comprised of polygons, which approximate the surface of a true continuous shape. Surface normal at a vertex is then at best an approximation of the normal of true surface.

Question 22

Define

• Luminance threshold
• Contrast threshold
• Sensitivity

Answer 22

Luminance threshold: The smallest detectable difference in luminance for a given background luminance.

Question 23

Define the forward display model.

Answer 23

Turns pixel values into corresponding luminance.