[ ans ]
Name: _______________________________
Student ID: _______________________________

Total points: 110
  1. Name at least three of the groundbreaking innovations in Engelbart's NLS prototype demonstration in 1968. [3]
    mouse, windowing system, hyperlinks, chording keyboard, collaborative work (email, IM, video conf)
  2. Describe Flynn's taxonomy of parallel computing. (Give more detail than just expanding the acronyms!) [6]
    SISD:
    regular serial uniprocessor computing
    SIMD:
    multiple processors each doing the same task, but on different parts of the data. Vector processing.
    MISD:
    the same data being run through different operations in parallel. Certain kinds of image processing, perhaps encryption breaking. Rarely used.
    MIMD:
    multiple processors doing different tasks on different data. Most general form of parallel computing; also most common nowadays.
  3. 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.
  4. We have occasionally considered linking together all 22 computers in the main lab to behave as one clustered parallel computer. Each computer has its own RAM and hard disk, as well as a dual-core CPU, and a Gigabit Ethernet connection to a single network switch that serves all 22 computers. Which of the three memory models from the previous question would make the most sense for such a cluster? What kind of programs could fully utilize such a cluster? Describe the behaviour of such programs and explain why such a cluster would be an appropriate system on which to run them. [6]
    Hybrid (shared+distributed) memory would make the most sense for a cluster: there are high-speed symmetric links between cores of the same CPU, but the links between nodes/computers are relatively slow. Programs that would run well on this should not need to communicate large volumes of data between nodes. Each node may utilize several hundred GB of local space, but should not be sending GB of data over the network. A GigE LAN could support frequent small messages between nodes, but not large volumes of data (even infrequently). An example application could be a numerical simulation of weather, where each node works on a block of the atmosphere -- the communication between nodes just deals with the edges of the blocks. Another application could be 3D rendering, where each node renders a part of the geometry in the scene, which is then composited together.
  5. The four main kinds of OpenMP synchronization #pragmas are parallel, critical, single, and barrier. Describe each of these and contrast them. [6]
    parallel: Each thread runs a separate copy of the following block of code. Variables declared beforehand are shared; variables declared within the parallel block are private to each thread.
    critical: The following block is run by each thread one at a time; no threads run the block at the same time with each other. This is useful if the threads need to access a shared resource.
    single: The following block is run by only one thread. The difference with critical is whether there are many copies or just one copy of the block being run.
    barrier: A barrier is a synchronization point; execution halts at this point until all threads have caught up.
  6. What are the RGB and CMYK colour spaces? What is the difference between them? What are they used for? Why are R, G, and B called the "primary" colours? [5]
    RGB is an additive colour space; adding more R, G, and B brings the mixture closer to white. RGB are primary colours because the human eye has light- receptor cells whose frequency response curves peak around those colours. CMYK is the subtractive colour space which is complementary to RGB: cyan is the opposite of red, magenta of green, and yellow of blue. CMYK is used for dyes and inks: adding more of the colours brings the mixture closer to black. Since black is often used, a fourth ink 'K' is dedicated to black.
  7. Describe the four types of lights offered by OpenGL. List all the properties for each type of light. [8]
    Point:
    has a location and RGBA 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.)
  8. In geometry, what is the difference between a point and a vector? Aren't they both just tuples of 3 floats? [2]
    A point represents a location in space, with no direction. A vector represents a direction and magnitude, with no location.
  9. Write a C/C++ function that takes two points in normalized mouse coordinates (x0,y0,x1,y1) and finds the axis-angle (vector-angle) representation of the virtual trackball rotation. Normalize mouse coordinates are floats in the range 0 to 1. Such an axis-angle representation could, for example, be passed to glRotate() to create a 4x4 rotation matrix. You may assume the presence of 3D-vector helper functions normalize(), magnitude(), dotproduct(), and crossproduct(), as well as sqrt(). Syntax is not as important as concept/pseudocode. [6]
    void getAxisAngle(float x0, float y0, float x1, float y1, float& axis, float& ang) {
    	float vec0[3], vec1[3], xprod[3];
    	vec0[0] = x0; vec0[1] = y0;
    	vec1[0] = x1; vec1[1] = y1;
    	vec0[2] = sqrt(1 - x0*x0 + y0*y0);
    	vec1[2] = sqrt(1 - x1*x1 + y1*y1);
    	xprod = crossproduct(vec0, vec1);
    	axis = normalize(xprod);
    	ang = arcsin(magnitude(xprod));
    }
    
  10. What is an environment map, and what is it used for? [4]
    Reflections in specular surfaces use colours taken from an image, to simulate the reflection of a complex scene in a shiny object.
  11. What is mip-mapping? Why is it cool? [4]
    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.
  12. Describe how you might implement Phong shading using vertex/fragment shaders. What variables do the shaders need? Should they be uniform, attribute, or varying? Exact GLSL code is not necessary; just provide a high-level description of what the vertex and fragment shaders would do. [5]
    Vertex shader computes vector to light and reflection vector (as varying). Rasterizer interpolates those over the fragment. Fragment shader uses interpolated light and reflection vectors, together with material properties, to calculate final shade.
  13. 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.
  14. What is a NURBS? Explain each part of the acronym in detail. (Hint: it is not plural!) [6]
    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.
  15. What are quadric surfaces? Why do raytracers like to use them? List some examples of quadric surfaces. [5]
    A quadric is any implicit surface that is defined by a quadratic (degree 2 polynomial) in x, y, and z. Examples include spheres, ellipses, cylinders, cones, and hyperboloids. The ray-surface intersection test, so critical in raytracing, is analytically solvable for quadrics, using the quadratic formula. As a result, finding intersections with quadrics is relatively easy, which speeds up raytracing.
  16. Expand the acronym BRDF and explain what it is. What are its inputs, and what is its output? [4]
    Bidirectional reflectance distribution function: defines what fraction of the incoming flux density along the given incoming direction is reflected along the given outgoing direction. Inputs: position along surface, incoming ray, outgoing ray. Output: scalar (fraction of flux density).
  17. What simplifying assumption is made about BRDFs in classical radiosity? Describe a real-world surface that might have BRDF that violates this assumption. [4]
    Radiosity assumes Lambertian surfaces, which means that the BRDF is constant across all incoming and outgoing directions. This constant is called the albedo. Non-Lambertian surfaces include any shiny surface (specular highlight), brushed aluminum (the direction of brushing affects the BRDF), etc.
  18. 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).
  19. What are scene graphs? Why are they cool? Describe an example. [4]
    Hierarchical grouping of 3D objects: geometry (e.g., triangle meshes), transforms (e.g., rotation, translation), material properties (e.g., colour). Allows grouping of related objects, as well as chaining of transforms. E.g., an Arm might have a shoulder rotation, then the upper arm, then an elbow rotation, then the forearm, then a wrist rotation, then the hand, etc. The entire arm can be moved by adjusting the shoulder rotation, rather than moving each vertex individually.
  20. A simple "Monte Carlo" estimate of π is to generate random points (x,y) within the unit square (i.e., 0≤x<1 and 0≤y<1) and count how many points lie within the unit quarter-circle (i.e., x2+y2 < 1). (This is a crude way of calculating areas.) The fraction (very slowly) approximates π/4. This problem is ripe for parallelization. Write an OpenMP program to estimate π/4 in this way. [6]
    See pi-monte.cpp.
  21. Describe at least four distinct principles of user-interface design. (There is flexibility here, but the principles should not overlap or be restatements of the same thing.) [4]
    Fitt's Law; know your users; be consistent with colours/names/layout; use metaphors carefully; use multiple levels of complexity/visibility (safety vs. control); always show current state (don't leave user hanging); design around the epicentre; save user's work; etc.
  22. Using the design principles you described above and others, critique the user interface of Word 2007. A screenshot is below to remind you, but you may draw upon your own experience with the program, not just what's in the screenshot. Be as specific as possible, and reference which user design principles you feel the program follows or violates. Talk about both positive and negative aspects. [6]