[ answers on web ]
Name: _______________________________
Student ID: _______________________________

Total points: 115
  1. Describe at least three of the innovations developed at Xerox's PARC in the 1970s. [3]
    Alto, Star microcomputers; WIMP model; desktop paradigm; Smalltalk language+IDE+runtime



  2. What are events and callbacks? Describe an example. [3]
    An event is an action, usually triggered by the user: e.g., clicking on a button, selecting a menu item, pressing Enter, moving the mouse. A callback is a procedure/function invoked when a corresponding event happens. For example, the exit() function might be run when the user clicks on a "Quit" button.





  3. Describe Fitt's law in words. What three quantities does it relate? [3]

    The time to acquire a target is a (logarithmic) function of (the ratio of) the distance and the size of the target.




  4. In light of Fitt's law, discuss the current application paradigm of menus (File->Open, etc.), and propose some ideas/replacements to make menus easier and faster to use. Discuss why your idea would be better in light of Fitt's law.[5]
    MS auto-hide, auto-reordering by use frequency, variable-size menu items, pie menus, etc.










  5. Discuss your experience with programming in OpenMP. Would you recommend it to other programmers wishing to do parallelism? Why or why not? [4]
    Pros of OpenMP: ease of programming; compile w/o OpenMP and get a correct uniprocessor program; pretty good compiler support.
    Cons of OpenMP: does not scale well to large systems: shared-memory assumption fails to take into account communication/network costs. Fine-grain control over threads and communication is more difficult than in MPI.







  6. Come up with your own non-computer-related analogy to explain each category of Flynn's taxonomy of parallel computing to a non-computer-scientist. [5]
    SISD:
    one bank teller serving customers one at a time.
    SIMD:
    several bank tellers serving multiple customers in parallel, but all doing the same tasks.
    MISD:
    one customer with complex needs, so several bank employees are working on the customer's account together.
    MIMD:
    many bank tellers and many customers; each customer's needs are different.












  7. Describe the (1) shared, (2) distributed, and (3) hybrid memory models of parallel computing. Draw the diagrams illustrating how memory and processors are tied together. What are the advantages/disadvantages of shared memory vs. distributed memory models? [6]
    Shared:
    All processors share same address space for main memory. The assumption is that memory access times are the same for all processors. Easier to program: threads communicate simply by sharing data structures directly. For small numbers of processors, often faster due to less overhead. Does not scale well.
    Distributed:
    Each processor has its own address space. No data structures can be shared with other processors. All communication must be explicit via networking, which makes programming more complicated due to synchronization and latency issues. Scales to hundreds of thousands of processors.
    Hybrid:
    Each node has a few (often 4-8) processors which share that node's memory. Nodes cannot directly see the memory of other nodes.










  8. Describe Amdahl's law of parallel computing. What is the take-home message? [4]

    Speedup = 1 / ( P/N + (1-P) ), where P is the fraction of code that is parallelizable, and N is the number of processors.
    Take-home message is that the important thing is not just the number of processors we throw at a problem, but the fraction of code that can be parallelized efficiently.



  9. Describe some reasons why parallelizing a problem across 1000 processors might not result in a 1000x speed-up. Discuss issues that need to be considered in designing parallel programs. [5]
    Not all the code is parallelizable: P in Amdahl's law. Overhead in starting new threads/tasks. Communication between processors: e.g., message-passing. Data dependencies -- some threads must wait for other threads to finish. Network may be a bottleneck. Synchronization between threads -- locks, shared resources. Load balancing -- some processors may sit idle.










  10. What is colour? Is an RGB triple (e.g., "#00FF77") a colour? Discuss. [3]
    Colour is a distribution of light energy across the visible spectrum ("frequency distribution"). An RGB triple is a point in a colour space, a combination of three chromaticities. Without specifying what those chromaticities are or how they are combined, an RGB triple is not a colour.




  11. Describe the stages of the OpenGL rendering pipeline. There is some flexibility in how to divide the stages, but describe the operations that must happen to get from geometry (GL primitives) to what we see on screen. [6]
    (1) Vertex processing:
    Transform vertex and normal via model-view matrix, per-vertex lighting calculation (for Gouraud), projection matrix
    (2) Assembly/clipping:
    Connect vertices into primitives, view frustum culling, clip against view volume
    (3) Rasterizer:
    Convert into pixel grid, interpolate per-vertex values across the primitive
    (4) Fragment processing:
    Per-fragment calculations, textures
    (5) Blending:
    Hidden-surface removal (depth buffer) and blending, final output to framebuffer








  12. Describe back-face culling. Why is it a good idea? When might it be a bad idea? [3]
    Back-face culling removes polygons whose normal vectors point away from the camera. The idea is that in a closed object, all polygons that point away from the camera are on the back side of an object and are occluded by front-facing polygons, so we won't see them, so they don't need to be rendered, so we can delete them from the graphics pipeline, which speeds up our rendering.



  13. Tell me everything you know about OpenGL transform matrices. [4]
    Represent rotations, translations, scaling, and affine projection transformations applied to both points and vectors in 3D space. Matrices are 4x4 so as to apply to 4-vector homogeneous coordinates. OpenGL uses two main matrices: the model-view matrix, which describes the relationship between the world and the camera, and the projection matrix, which describes how the 3D world is flattened onto a 2D image plane.





  14. Recall that glutSolidTeapot(1.0) draws a teapot of size 1 centred at the origin. Given the following sequence of OpenGL code, where is the teapot centred, in world coordinates? [2] 
    	glMatrixMode( GL_MODELVIEW );
	glLoadIdentity();
	glScalef( 3.0 );
	glTranslatef( 3.0, -1.0, 5.0 );
	glScalef( 0.5 );
	glutSolidTeapot( 1.0 );
    The teapot is centred about (9.0, -3.0, 15.0).
  15. Continuing the previous problem, write out the 4x4 model-view matrix produced by this code. (Do the math; your final answer should be only one matrix.) [4]
    1.5 0 0 9
    0 1.5 0 -3
    0 0 1.5 15
    0 0 0 1






  16. What are quaternions and how are they used in computer graphics? [4]
    Quaternions are a 4D Clifford algebra (extension of the complex numbers) having one real part and three imaginary parts: a typical quaternion might be, e.g., 3 + 6i - 5j + 0.2k. Quaternion multiplication is associative but not commutative. The unit quaternions are used to represent rotations in 3D; composition of rotations is simply multiplication of the corresponding quaternions.




  17. Describe the four types of lights offered by OpenGL. (Hint: this is not talking about the Phong lighting model!) What parameters are used to define each type of light? [5]
    Point:
    has a location and colours (ambient, diffuse, specular). Similar to a candle.
    Directional:
    has a direction and colours, but no location. Similar to the sun. Specified in OpenGL the same way as point lights, but using homogeneous coordinates to specify a vector instead of a point.
    Spot:
    has a location, direction, cutoff depth, falloff exponent, and colours. Similar to a theatre spotlight.
    Global ambient:
    We can specify an ambient light that uniformly illuminates the whole scene. Similar to a very evenly lit scene like an open field on a cloudy day.
    (Area light):
    (not offered by OpenGL, but we can model it using global illumination techniques like radiosity.)
    (Emissive):
    (Emissive OpenGL objects don't count as lights because they don't cast light on other objects.)








  18. Contrast texture maps, bump maps, and environment maps. [6]
    Texture map:
    an image pasted on a surface in 3D. Colours of the surface are taken from the image.
    Bump map:
    the normal vectors on the surface are wobbled to simulate a perturbation of the surface (in/out) by an amount given in the bump map image.
    Environment map:
    reflections in specular surfaces use colours taken from an image, to simulate the reflection of a complex scene in a shiny object.












  19. What is mip-mapping? Why is it cool? [3]
    Mip-maps are precalculated smaller versions of the texture at various levels of detail. e.g., a version with half the length and half the width; another version with one-quarter the length and one-quarter the width, etc. They are used in texture mapping to avoid aliasing: unsightly jagged edges and artifacts that would otherwise occur when the texture's projected fragment on the screen is very small.



  20. Describe the tasks of vertex shaders and fragment shaders. What are the inputs to each? What are the outputs from each? [5]
    Vertex shaders: per-vertex transform and lighting calculations.
    Input: vertex information: position, normal vector, texture coords, global OpenGL state, etc.
    Output: transformed vertex in eye coordinates, transformed vectors, any per-vertex colouring, etc.
    Fragment shaders: per-fragment (per-pixel) calculations.
    Input: interpolated per-fragment colour, vectors and other varying attributes from the vertex shader; global OpenGL state.
    Output: final per-fragment colour, ready for blending.








  21. Describe and contrast the three types of global variables in GLSL: uniform, attribute, and varying. (GLSL also has a fourth option, const.) [5]
    uniform:
    per-primitive. Constant across whole primitive, or world-wide. Read-only for both vertex+fragment shaders.
    attribute:
    per-vertex. Read/write for vertex shader; inaccessible by fragment shader.
    varying:
    per-vertex/per-fragment. Used to pass data from vertex shader to fragment shader. Writable by vertex shader; values are then interpolated by the rasterizer and made available read-only for the fragment shader.








  22. Contrast interpolating cubic polynomial curves, Hermite curves, and Bezier curves. For each type of cubic polynomial curve, what information is needed to uniquely specify a curve? [6]
    Interpolating:
    Specify four points; the curve goes through all four.
    Hermite:
    Specify positions and tangent/velocity vectors at the start and end of the curve.
    Bezier:
    Specify four Bezier control points. Two are the start and end of the curve (interpolated). The other two control points are used to derive the velocity vectors (3 times the difference vector) for the start and end points.







  23. Draw a non-trivial set of four control points and use deCasteljau's algorithm to estimate the points at u=1/3 and u=2/3. Show your work (you may want to draw two copies to work on). Sketch the Bezier curve. "Trivial" sets of control points include all four points at the same location, all collinear, etc. [4]


















  24. What is the convex hull property of Bezier curves? Demonstrate it on the sketch of your Bezier curve from the previous problem. [2]
    The convex hull property states that the entire Bezier curve segment lies within the convex hull of its four control points. (This property still holds for 2D Bezier surface patches, and also in 3D!)



  25. Describe and contrast C0, C1, C2, and G1 continuity for splines. [4]
    C0:
    Curve segments touch; basic continuity.
    C1:
    Curves touch and velocity vectors also match at the joins
    C2:
    Curves touch, velocity vectors match, and even the curvatures match at the joins
    G1:
    Curves touch, and velocity vectors point in the same direction (but might not be the same magnitude). In between C0 and C1.










  26. What is a NURBS? Explain each part of the acronym in detail. [5]
    NU (non-uniform):
    the knots (joins between Bezier segments) need not be uniformly spaced in u (the parameter space). For instance, this can be used to make the NURBS interpolate its endpoints, by repeating knots four times at the start (u=0) and end (u=1).
    R (rational):
    Each control point has a relative weighting associated with it which biases its influence on the curve.
    BS (B-spline, Bezier spline):
    A B-spline is a spline made up of cubic Bezier segments, joined in a particular way so as to get C2 continuity.











  27. Describe and contrast: spatial grids, octrees, k-d trees, and BSP trees. [6]
    Grids:
    subdivide space into equal voxels, regularly spaced
    Octrees:
    Adaptive subdivision: where needed, each cell is subdivided into eight equal subcells along the coordinate axes.
    k-d trees:
    Also adaptive like octrees, but cells are subdivided along one axis at a time. Cells need not be split into equal-size subcells.
    BSP trees:
    Even more flexible than k-d trees: each time a cell is split using a (k-1)-dimensional hyperplane (a regular plane in 3D), oriented in any way (need not be along a coordinate axis).