# Computer Graphics (CS4300) 2011F: Exam 1 Example Problems

Exam 2 covers all material from lecture 14 through the last lecture of the semester.

### Lecture 15 - Splines

• What is the difference between a general cardinal spline and a Catmull-Rom spline?
• Given points (x0, y0), (x1, y1), (x2, y2), (x3, y3), (x4, y4) with x0 < x1 < x2 < x3 <x4, give formulas that define
1. the 4th degree polynomial through the points.
2. the Hermite geometry for the cubic curve starting at (x1, y1) and ending at (x2, y2) that is part of the Catmull-Rom spline through the points.
3. the Bezier geometry for the cubic curve starting at (x1, y1) and ending at (x2, y2) that is part of the Catmull-Rom spline through the points.
• How mant cubic curves are needed to define the Catmull-Rom spline through the points (x0, y0), (x1, y1), (x2, y2), (x3, y3), (x4, y4)?
• Give reason(s) why the Catmull-Rom spline through these points is preferable to the 4th degree polynomial through them.
• When might the 4th degree polynomial through them be preferable?

### Lectures 17, 18, and 19. Bezier Curves and Casteljau Algorithm

• Sketch the control polygon for for a cubic Bézier curve with one bend. Also sketch the curve itself.
• Same as above but with two bends.
• State at least two useful properties of Bézier curves.
• Given the vertices of the control polygon of a cubic Bézier curve, how would you transform the curve by the homogeneous transformation matrix ?
• Explain what is meant by the “convex hull” property of Bézier curves, and suggest how it could be used to quickly check if two Bézier curves do not intersect.
• Given a drawing of a cubic Bézier curve and its control polygon label all six points generated in the de Casteljau algorithm for evaluating the curve at including the evaluated point labeled . Sketch in all these points and the associated line segments. The de Casteljau algorithm also generates the vertices of control polygons for two cubic Bézier curves that subdivide the original curve at . What are the vertices of the control polygon for the subdivided curve from to ? From to ?

### Lectures 22 and 23. Polymesh

• Write pseudocode that calculates the “minimum” and “maximum” corners of an axis-aligned bounding box for a list of triangles .
• Given the “minimum” and “maximum” corners of an axis-aligned bounding box , show one method to compute the center and radius of a bounding sphere that encloses .
• Planar Polygon Test: Given a sequence of n points P1, ..., Pn in in three dimensions, give pseudo-code for a boolean function Planar(P1, ..., Pn) that returns true if and only if the points lie in a common plane. Comment the code to indicate what it is doing.
• Let be a list of triangle meshes , where every is an individual 3D triangle (mesh contains triangles). Let be a 3D ray. Assume you have algorithms
• that takes in a triangle mesh and returns a bounding sphere for that mesh
• that returns true if intersects triangle and false otherwise
• that returns true if intersects sphere and false otherwise
Write two pseudocode procedures
• that is called (by other code that you do not have to write) whenever any triangle in any mesh is added, removed, or changes position, and that can create or update a global datastructure to be used to accelerate picking (it is up to you to define this global datastructure)
• that is called whenever the user has clicked the mouse (by other code that you do not have to write) with a corresponding pick ray, and that returns one of the meshes that was intersected by that pick ray, if any, or otherwise (if more than one mesh is intersected, you may return any of them).
For full credit, you must not call on any triangle in a mesh unless would also return true.
• Define frustum culling, backface culling, and occlusion culling.
• Given three 3D points that appear in CCW order from some camera viewpoint, show one method to determine if another 3D point is on the near side or the far side of the plane through with respect to the camera.
• You are given a sketch of a 3D triangle with vertices that is cut by a plane such that are on one side of the plane and is on the other side, splitting the original triangle into one trapezoid and one smaller triangle . The intersection of the plane with the triangle is a line segment with endpoints where is on the side of the triangle between and and is on the side between and Assume that from some camera appear in CCW order. (a) What are the vertices of the trapezoid as they would appear to the same camera in CCW order? (b) What are the vertices of the smaller triangle as they would appear to the same camera in CCW order? (c) Split into two triangles by sketching in one of its diagonals, and give the vertices of these triangles in CCW order as they would appear to the same camera.

### Lectures 24, 25, 26. RaycastingLecture 27 Intersections

• We studied a shading model that included separate ambient, diffuse, and specular components. Consider a scene with a single sphere illuminated by one ambient light with intensity and one directional light with intensity . The ambient light only contributes to the ambient shading term; the directional light contributes to the diffuse and specular shading terms, but not ambient. Several pictures are given of the scene with different settings of the following variables
• or
• or
• specular shading enabled or disabled
Mark the value of each of those three variables that must have been in effect to produce each picture.
• Assume you have
• a list of “surface” objects in world frame
• a function that can create a 3D ray in world frame that starts at the location of a camera and goes through image plane pixel
• a function that returns a scalar that is either the nearest intersection of a ray with a surface , or if the ray does not intersect the surface
• a function that sets the color of pixel to the ambient color of surface .
Write pseudocode for a basic ray tracer that sets each pixel in a canvas to the ambient color of the nearest surface, or to black if no surface is intersected by a ray from the camera through that pixel.
• Assume you have
• a list of “surface” objects in world frame
• a point light at location in world frame
• a function that returns a scalar that is either the nearest intersection of a ray with start point and direction with a surface , or if the ray does not intersect the surface (i.e. if then the intersection point is ; note that and are both given in world frame, and that does not necessarily need to be a unit vector)
Write pseudocode that determines if the point light is in shadow at a given point on some surface .
• (a) State the mirror reflection law. [Hint: you may want to use the phrases “angle of incidence” and “angle of reflection”.] (b) You are given a diagram showing a small patch of a 3D surface viewed side-on. The outward pointing surface normal at a point is shown as a unit vector . A unit vector from towards a camera is shown as . Give the math to compute , the component of perpendicular to the surface, and , the component of parallel to the surface. These should be set up so that . Sketch in and . (c) Give the math to compute , a unit vector in the direction that a ray from the camera would reflect after bouncing off the surface at according to the mirror reflection law. You may use and in your calculation of . Finally, sketch in .
• The triangle ABC is one of the triangles in an icosahedron, where . Assume there is a point light source located at LS = (1000, 1000, 1000).
1. What is the midpoint P of triangle ABC?
2. Give the outward unit normal vector N to triangle ABC at its midpoint P.
3. Give unit vector L from P to the light? Express your answer in terms of LS, and P.
4. Assume the icosahedron’s color is (250, 0, 0). Give the actual color that triangle ABC will be rendered in if ka = .2, kd = .6, and ks = 0.

### Lectures 28 and 29 Fractals, L-Systems

• Define Julia set.
Give pseudocode to draw a Julia set.
• Define Mandelbrot set.
Give pseudocode to draw a Mandelbrot set.
• What is the relationship between Julia sets and the Mandelbrot set.
• Prove that i is in the Mandelbrot set by showing that the iterates of 0 under the complex function f(z) = z2 + i eventually repeat, and so are bounded.
• Describe L-systems. What makes them well-suited for generating natural objects like trees and plants?
• Given the following L-System, show what is drawn at the levels indicated. Label your drawing to show the relative lengths of the line segments. Remember that the square brackets are push and pop symbols.
• Angle = 45°
• Start: FF
• Rule: F:FF[-FF]+F
1. Level 0 - Just from the start sentence
2. Level 1 – after one application of the rule.
• The first iterations (levels 1, 2, and 3) of a Gosper C-Curve are shown below. Give a rule to complete this L-system so that it will generate Gosper C-Curves.
• Angle = 45°
• Start: F
• Rule:

### Lectures 30 Perlin Noise

• Perlin noise is popular for generating natural phenomenon like marble or clouds. What makes Perlin noise better than other types of noise, such as white noise where every pixel is an independently sampled random number?
• Why is splined noise better than linear noise?
• What is the difference between turbulence and noise?
• Give pseudocode using 2D (Perlin) turbulence to generate a woody texture like the one to the right.

### Lectures 31 Bump and Texture Maps

• There are a large number of techniques for improving the realism of ray traced images. Briefly describe how each of the techniques below modifies the lighting calculation.
1. Texture Mapping
2. Bump Mapping
3. Solid Textures
Which of these techniques would be most appropriate for modeling each of the following?
1. A picture hung on a wall.
2. A marble statue.
3. A golf ball (with no logo).
4. A patterned tile floor.
5. The ripples created by dropping a stone in a pool of water.
6. A wooden table top.

### Lectures 32 Morphing

• The center image below is a morph of the mandril (left) and Mona (right). The sizes of the images are shown below them (width x height in pixels).

To blend the images, Mona must first be scaled to a 256 x 256 image.
1. Explain how this image is formed from the smaller image of Mona using the inverse map. (Give a formula for finding the color at a pixel (x, y) in the new image in terms of pixels in the original image.)
2. In particular, the center of Mona’s nose in the new image is at (88, 164). What are the coordinates of the pixel in the original picture that gets mapped to this point?

Last Updated:

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #WVH-340,
Boston, MA 02115

Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/CS4300/example-problems/example-problems-E2-Fall2011.html