# CG ECSE-4750 Computer Graphics Final Exam Solution, RPI, Tues 2018-12-18

Name, RCSID: WRF solutions

## 1   Grade statistics

1. Number of final submissions: 27
2. Highest score: 74
3. Lowest score: 44
4. Average score: 61.78
5. Median score: 64

## 2   Scatterplot of grade vs order of finish ## 3   Rules

1. You have 180 minutes.
2. You may bring in two 2-sided 8.5"x11" papers with notes.
3. You may not share material with each other during the exam.
4. No collaboration or communication (except with the staff) is allowed.
5. There are thirty six questions. Check that your copy of this test has all the pages.
6. Full score is 76.

## 4   Questions

1. _____/2 Put these graphics pipeline components in the correct order:

2. primitive-assembly 2nd
3. rasterizer 3rd
2. _____/2 Which of the following 3D rotation methods is vulnerable to gimbal lock?

1. Euler angles *
2. matrix
3. quaternion
4. vector
3. _____/2 In the OpenGL pipeline, the Primitive Assembler does what?

1. fits together pieces of ancient Sumerian pottery.
2. rotates vertices as their coordinate systems change.
3. creates lines and polygons from vertices. *
4. finds the pixels for each polygon.
5. reports whether the keyboard and mouse are plugged in correctly.
4. _____/2 When rotating an object, what can happen to an object?

1. Straight lines might turn into curves.
2. Straight lines stay straight, but angles might change.
3. Straight lines stay straight, and angles don't change, but distances may change, either longer or shorter.
4. Straight lines stay straight, and angles don't change, but distances might get longer.
5. Straight lines stay straight, and angles and distances don't change. *
5. _____/2 If i and j are quaternions, what is i+j?

1. -k.
2. 0.
3. 1.
4. i+j, there is no simpler representation. *
5. k.
6. _____/2 If i and j are quaternions, what is ij?

1. -k.
2. 0.
3. 1.
4. i+j, there is no simpler representation.
5. k. *
7. _____/2 The quaternion i represents what rotation?

1. 180 degrees about the x-axis. *
2. 90 degrees about the x-axis.
3. 180 degrees about the y-axis.
4. 90 degrees about the y-axis.
5. no change, i.e., 0 degrees about anything.
8. _____/2 The parametric equation of a line through the points (1,1) and (2,3) is:

1. P = (1,1) + t(1,0) + u(0,1)
2. P = (1,1) + t(1,1)
3. P = (1,1) + t(1,2) *
4. P = (1,1) + t(2,3)
5. P = t(1,1) + u(2,3)
9. _____/2 The normal vector of length one to the plane through the points (1,0,0), (0,1,0), (0,0,1) is

1. (1,0,0)
2. $\left( \frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}} \right)$ *
3. (-1, 0, 0)
4. 3
5. (1/3, 1/3, 1/3)
10. You call gl.BufferSubData to do what?

1. to add or replace part of the buffer in the GPU. *
2. to define a submarine object.
3. to subtract some data in the buffer.
4. to tell the GPU to look for a pattern and substitute any occurrences,
5. to tell the GPU to use a subroutine instead of the main program.
11. _____/2 Translating the 2D homogeneous point by (1,2,3) by (in Cartesian terms) dx=1, dy=2 gives which new homogeneous point?

1. (1,2,3)
2. (1,2,3,4)
3. (2,4)
4. (2,4,3)
5. (4,8,3) *

as Cart: (1/3,2/3)+(1,2) = (4/3,8/3)

12. _____/2 Rotating the 2D Cartesian point (0,1) by 90 degrees gives what:

1. (1,0)
2. (-1,0) * (corrected)
3. (0,1)
4. (0,-1)
5. (-.7,.7)
13. _____/2 Give me a matrix M that has this property: for all vectors p, $Mp = \begin{pmatrix}2&3&1\end{pmatrix} \times p$. The operator is the vector cross product.

$\begin{pmatrix}0 & -1 & 3 \\ 1 & 0 & -2\\ -3 & 2 & 0 \end{pmatrix}$

14. _____/2 In a fragment shader, a sampler2D does something more than a simple array lookup like you have in most programming languages. What?

If the subscripts are fractions, this blends the adjacent texels.

15. _____/2 Tell me about view normalization. What is it? What is good about it?

Transforms the scene and the projection together to make the projection orthogonal down one axis and the clip region a 2x2x2 cube centered on the origin. However a cube in the scene becomes a truncated pyramid. The simpler projection and clip polyhedron are a win. E.g., the hardware is simpler.

16. _____/4 Compute the projection equations when the viewpoint is at (0,0,0) and the projection plane is 2x+y+z=4. Use Cartesian coordinates. You do not need to put the result into a matrix form, but simplify your result as much as possible.

The projection will be a scaling since the center is at the origin. Point (x,y,z) will scale to (ax,ay,az) where 2ax+ay+az=4, so a=4/(2x+y+z). So, the projection is:

x' = 4x/(2x+y+z), y' = 4y/(2x+y+z), z' = 4z/(2x+y+z),

You could start with the matrix mentioned in class and end with this:

$\left( \begin{array}{cccc} 4 &0&0&0\\ 0&4&0&0\\ 0&0&4&0 \\ 2&1&1&0 \end{array} \right)$

17. _____/2 Name the algorithm that was designed to rasterize a circle using only integer additions, subtractions, and shifts.

Bresenham's circle algorithm.

18. _____/2 In a shader, what is the difference between a uniform variable and a varying variable?

A uniform variable is a global constant that is the same for all vertices. A varying variable is computed in the vertex shader and then interpolated across the polygon to give a value at each fragment that is input to the fragment shader.

19. _____/2 Give 2 reasons why we usually use a sequence of low-degree curves instead of one high degree curve.

No local control: changing one control point can change the whole curve. Badly conditioned matrix: a small change in a control point can cause a big change in the curve. Sensitivity to numerical roundoff errors.

20. _____/2 What does the word rational mean in NURBS?

NURBS use homogeneous coordinates, so their Cartesian X, Y, and Z are ratios.

21. _____/2 What is the difference between Phong shading and Gouraud shading?

Gouraud shading computes a color for each vertex and then interpolates it across the polygon (face). Phong shading starts with a surface normal at each vertex of the polygon and interpolates an approximate normal for each pixel of the polygon. Then, in the fragment shader, this approximate normal is normalized an input into the lighting equation that is the subject of the following question.

22. _____/2 In the Phong lighting model, which computes the color or brightness of each pixel, how do you make a surface material more metallic or shiny?

The shininess is the exponent of the dot product of the view vector and reflected vector. Higher means shinier.

23. _____/2 Where is the 3D homogeneous point (1,0,0,0)?

At infinity in the Cartesian direction (1,0,0). Informally, at the end of the positive X axis. The limit of the Cartesian point sequence (x,0,0) as x approaches infinity. The center of projection for a parallel projection down the X axis.

24. _____/2 Consider a 2D cubic Bezier curve with Cartesian control points (0,0), (1,1), (2,2), (3,3). What is the point at t=0.5?

1/8 (0,0) + 3/8 (1,1) + 3/8 (2,2) + 1/8 (3,3) = (3/2, 3/2)

25. _____/2 Describe what the curve in the previous question looks like.

A straight line from (0,0) to (3,3).

26. _____/2 What is Constructive Solid Geometry?

Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine simpler objects - Wikipedia.

27. _____/2 What texture mapping problem does the mipmap solve?

The projected size of the texels are usually not close to the size of the pixels. This is a problem because: If the texels are smaller than the pixels, aliasing issues arise. If larger, then several adjacent pixels will be the same color, making the image look posterized. Mipmaps solve this by precalculating a pyramid of texture maps that are coarser and coarser.

28. _____/2 Mathematically, the aliasing problem in CG

1. happens when high frequency signals are not sampled often enough.
2. happens when low frequency signals are sampled too often.
3. is a new problem that did not occur with the old displays.
4. can be reduced by subsampling and averaging
5. both (a) and (d). *
29. _____/2 About polygon clipping:

1. A polygon might gain vertices. *
2. A polygon might gain area.
3. If a polygon's vertices are all outside the clip region, then it may be deleted.
4. Using a 6-stage pipeline keeps the latency the same.
5. Concave polygons become convex.
30. _____/2 A small light source that is twice as far away is 1/4 as bright. That is, there is an inverse square fall off for brightness. However, when modeling light in graphics, we usually don't do that. Why?

Various reasons. The dynamic range of brightness in the scene would then be too great. If the light is bigger than a point and we're not too far away, or if there is ambient light, then the brightness falls off more slowly.

31. _____/2 What tool maps spectral colors into a human perceptual coordinate system? Your use it to determine the visual result of mixing colors.

The CIE Chromaticity diagram.

32. _____/2 With a B-spline, the joints are usually invisible because the two segments meet with C2 continuity. Sometimes a designer may want there to be a visible kink at a joint, i.e., wants only C0 continuity. How can that be achieved?

To reduce C2 continuity to C0 continuity at a joint, make 3 control points coincide.

33. _____/2 What's the hardest part of implementing the painters algorithm?

Sorting the polygons back to front. This is always hard if they overlap in Z and sometimes impossible. Then you have to split a polygon.

34. _____/2 Consider a cube. It has both geometry and topology. What is the geometry and what is the topology?

Geometry: the positions of the vertices. Topology: which vertices (i.e., their id numbers) make up the edges and faces.

35. _____/2 Name the javascript WebGL function that sets the current buffer for future buffer operations.

bindBuffer

36. _____/2 Name the javascript WebGL function that declares that the current buffer contains 3 floats per vertex (or generally some number of some type per vertex).

vertexAttribPointer

End of final exam. Total: 76 points.

# CG ECSE-4750 Computer Graphics Final Exam, RPI, Tues 2018-12-18

Name, RCSID:

.

.


Rules:

1. You have 180 minutes.
2. You may bring in two 2-sided 8.5"x11" papers with notes.
3. You may not share material with each other during the exam.
4. No collaboration or communication (except with the staff) is allowed.
5. There are thirty six questions. Check that your copy of this test has all the pages.

Questions:

1. _____/2 Put these graphics pipeline components in the correct order:

2. primitive-assembly
3. rasterizer
.

.

2. _____/2 Which of the following 3D rotation methods is vulnerable to gimbal lock?

1. Euler angles
2. matrix
3. quaternion
4. vector
.

.

3. _____/2 In the OpenGL pipeline, the Primitive Assembler does what?

1. fits together pieces of ancient Sumerian pottery.
2. rotates vertices as their coordinate systems change.
3. creates lines and polygons from vertices.
4. finds the pixels for each polygon.
5. reports whether the keyboard and mouse are plugged in correctly.
.

.

4. _____/2 When rotating an object, what can happen to an object?

1. Straight lines might turn into curves.
2. Straight lines stay straight, but angles might change.
3. Straight lines stay straight, and angles don't change, but distances may change, either longer or shorter.
4. Straight lines stay straight, and angles don't change, but distances might get longer.
5. Straight lines stay straight, and angles and distances don't change.
.

.

5. _____/2 If i and j are quaternions, what is i+j?

1. -k.
2. 0.
3. 1.
4. i+j, there is no simpler representation.
5. k.
.

.

6. _____/2 If i and j are quaternions, what is ij?

1. -k.
2. 0.
3. 1.
4. i+j, there is no simpler representation.
5. k.
.

.

7. _____/2 The quaternion i represents what rotation?

1. 180 degrees about the x-axis.
2. 90 degrees about the x-axis.
3. 180 degrees about the y-axis.
4. 90 degrees about the y-axis.
5. no change, i.e., 0 degrees about anything.
.

.

8. _____/2 The parametric equation of a line through the points (1,1) and (2,3) is:

1. P = (1,1) + t(1,0) + u(0,1)
2. P = (1,1) + t(1,1)
3. P = (1,1) + t(1,2)
4. P = (1,1) + t(2,3)
5. P = t(1,1) + u(2,3)
.

.

9. _____/2 The normal vector of length one to the plane through the points (1,0,0), (0,1,0), (0,0,1) is

1. (1,0,0)
2. $\left( \frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}} \right)$
3. (-1, 0, 0)
4. 3
5. (1/3, 1/3, 1/3)
.

.

10. _____/2 You call gl.BufferSubData to do what?

1. to add or replace part of the buffer in the GPU.
2. to define a submarine object.
3. to subtract some data in the buffer.
4. to tell the GPU to look for a pattern and substitute any occurrences,
5. to tell the GPU to use a subroutine instead of the main program.
.

.

11. _____/2 Translating the 2D homogeneous point by (1,2,3) by (in Cartesian terms) dx=1, dy=2 gives which new homogeneous point?

1. (1,2,3)
2. (1,2,3,4)
3. (2,4)
4. (2,4,3)
5. (4,8,3)
.

.

12. _____/2 Rotating the 2D Cartesian point (0,1) by 90 degrees gives what:

1. (1,0)
2. (-1,0)
3. (0,1)
4. (0,-1)
5. (-.7,.7)
.

.

13. _____/2 Give me a matrix M that has this property: for all vectors p, $Mp = \begin{pmatrix}2&3&1\end{pmatrix} \times p$. The operator is the vector cross product.

.

.

14. _____/2 In a fragment shader, a sampler2D does something more than a simple array lookup like you have in most programming languages. What?

.

.

15. _____/4 Tell me about view normalization. What is it? What is good about it?

.

.

16. _____/4 Compute the projection equations when the viewpoint is at (0,0,0) and the projection plane is 2x+y+z=4. Use Cartesian coordinates. You do not need to put the result into a matrix form, but simplify your result as much as possible.

.

.

17. _____/2 Name the algorithm that was designed to rasterize a circle using only integer additions, subtractions, and shifts.

.

.

18. _____/2 In a shader, what is the difference between a uniform variable and a varying variable?

.

.

19. _____/2 Give 2 reasons why we usually use a sequence of low-degree curves instead of one high degree curve.

.

.

20. _____/2 What does the word rational mean in NURBS?

.

.

21. _____/2 What is the difference between Phong shading and Gouraud shading?

.

.

22. _____/2 In the Phong lighting model, which computes the color or brightness of each pixel, how do you make a surface material more metallic or shiny?

.

.

23. _____/2 Where is the 3D homogeneous point (1,0,0,0)?

.

.

24. _____/2 Consider a 2D cubic Bezier curve with Cartesian control points (0,0), (1,1), (2,2), (3,3). What is the point at t=0.5?

.

.

25. _____/2 Describe what the curve in the previous question looks like.

.

.

26. _____/2 What is Constructive Solid Geometry?

.

.

27. _____/2 What texture mapping problem does the mipmap solve?

.

.

28. _____/2 Mathematically, the aliasing problem in CG

1. happens when high frequency signals are not sampled often enough.
2. happens when low frequency signals are sampled too often.
3. is a new problem that did not occur with the old displays.
4. can be reduced by subsampling and averaging
5. both (a) and (d).
.

.

29. _____/2 About polygon clipping:

1. A polygon might gain vertices.
2. A polygon might gain area.
3. If a polygon's vertices are all outside the clip region, then it may be deleted.
4. Using a 6-stage pipeline keeps the latency the same.
5. Concave polygons become convex.
.

.

30. _____/2 A small light source that is twice as far away is 1/4 as bright. That is, there is an inverse square fall off for brightness. However, when modeling light in graphics, we usually don't do that. Why?

.

.

31. _____/2 What tool maps spectral colors into a human perceptual coordinate system? Your use it to determine the visual result of mixing colors.

.

.

32. _____/2 With a B-spline, the joints are usually invisible because the two segments meet with C2 continuity. Sometimes a designer may want there to be a visible kink at a joint, i.e., wants only C0 continuity. How can that be achieved?

.

.

33. _____/2 What's the hardest part of implementing the painters algorithm?

.

.

34. _____/2 Consider a cube. It has both geometry and topology. What is the geometry and what is the topology?

.

.

35. _____/2 Name the javascript WebGL function that sets the current buffer for future buffer operations.

.

.

36. _____/2 Name the javascript WebGL function that declares that the current buffer contains 3 floats per vertex (or generally some number of some type per vertex).

.

.


End of final exam. Total: 76 points.

# CG Class 30, Wed 2018-12-12

Review before final exam.

# CG Class 29, Mon 2018-12-10

## Review?

Do you want a review in the Wed lab session?

# CG Class 27, Mon 2018-12-03

## 1   OpenGL in Guha vs WebGL in Angel

1. Guha, the text I used before Angel, uses OpenGL. Angel uses WebGL.

2. OpenGL has a C API; WebGL uses Javascript.

3. That OpenGL is the obsolete version 2; WebGL is based on the current OpenGL 3.

4. OpenGL 2 has an immediate mode design: you draw things and they are forgotten.

In WebGL you send buffers to the GPU and then draw them.

5. OpenGL has compute shaders and geometry shaders. They fill in points along Bezier curves and draw trimmed NURBS.

6. A NURBS surface is a 2D parametric surface in 3D (or 4D if homogeneous).

A trim line is a 1D parametric curve in the the 2D parameter space of the surface.

The trim lines cut around the outside of the desired region and also cut out holes.

This is a powerful technique.

## 2   Chapter 15 slides

1. You do not need to learn most of those slides. Later I'll summarize what you need.
2. 15_1 Global rendering.
3. 15_2 Ray tracing.
4. 15_3 What's next?.

# CG Class 26, Thurs 2018-11-29

## 2   Old OpenGL in C and with NURBS

Before Angel, I used another book, Guha. It used old OpenGL in C. However therefore it could show NURBS. Some sample programs are in

https://wrf.ecse.rpi.edu/wiki/ComputerGraphicsFall2013/guha/Code

Look at bezierCurves, which shows moving control points.

trimmedBicubicSplineSurface shows NURBS.

## 3   WebGL query

Victor Calvert writes,

The WebGL report shows current-environment specifics, including the maximum number of textures, maximum framebuffer resolution, and other information, retrieved via the WebGL API.

# CG Homework 11, due Mon 2018-12-03 2359

1. (2 pts) Computing the effect of light reflecting off of one diffuse surface onto the other surfaces in the scene is called:

1. Bitblt
2. Bump mapping
3. Environment mapping
5. Texture mapping
2. (2 pts) Painting a image onto a face to simulate fine detail is called:

1. Bitblt
2. Bump mapping
3. Environment mapping
5. Texture mapping
3. (2 pts) Pretending to alter the normal vectors to the surface during rendering is called:

1. Bitblt
2. Bump mapping
3. Environment mapping
5. Texture mapping
4. (2 pts) Quickly copying blocks of pixels from one buffer to another is called:

1. Bitblt
2. Bump mapping
3. Environment mapping
5. Texture mapping
5. (2 pts) Reflecting the objects around a shiny object onto its surface is called:

1. Bitblt
2. Bump mapping
3. Environment mapping
5. Texture mapping

6. (2 pts) Several coordinate systems are typically used in texture mapping. Which one may be used to model curves and surfaces?

1. Lagrangian coordinates
2. Object or World Coordinates
3. Parametric coordinates
4. Texture coordinates
5. Window Coordinates
7. (2 pts) Which one is used to identify points in the image to be mapped?

1. Lagrangian coordinates
2. Object or World Coordinates
3. Parametric coordinates
4. Texture coordinates
5. Window Coordinates
8. (2 pts) Which one is conceptually, where the mapping takes place?

1. Lagrangian coordinates
2. Object or World Coordinates
3. Parametric coordinates
4. Texture coordinates
5. Window Coordinates
9. (2 pts) Which one is where the final image is really produced?

1. Lagrangian coordinates
2. Object or World Coordinates
3. Parametric coordinates
4. Texture coordinates
5. Window Coordinates

10. (2 pts) Mathematically, the aliasing problem in CG

1. happens when high frequency signals are not sampled often enough.
2. happens when low frequency signals are sampled too often.
3. is a new problem that did not occur with the old displays.
4. can be reduced by subsampling and averaging
5. both 1 and 4.
11. (2 pts) When you add many images together to blend them, there may be problems: (10_3)

1. Loss of accuracy if each color has only 8 bits.
2. You can't do this at all in WebGL.
3. This requires using a color buffer of at least 4096x4096.
4. This requires a stencil buffer.
5. This requires that the A component be set to 0.0.
12. (2 pts) Fog has been removed from OpenGL, and is not in WebGL, because: (10_3)

1. The several possible fog factors (linear, exponential, gaussian) were too confusing.
2. With cleaner air, we no longer want to model smog.
3. It executed too slowly.
4. Removing it simplified the standard, and anyway you can implement it yourself.
5. It wasn't removed; it's still part of WebGL.
13. (2 pts) What does sampler2D do? (10_4)

1. Return a sample random variable from a probability distribution.
2. Return one specific texel from a texture map.
3. Return a point on a bezier curve by interpolating control points.
4. Interpoint a texture value from nearby texels.
5. Compute a phong-shaded color.
14. (2 pts) Rendering a scene by computing which pixels are colored by each object is called (12_5)

1. Image space approach
2. Modelview space approach
3. Object space approach
4. Pixel space approach
5. Viewport space approach
15. (2 pts) Rendering a scene by computing which objects are behind each pixel is called (12_5)

1. Image space approach
2. Modelview space approach
3. Object space approach
4. Pixel space approach
5. Viewport space approach
16. (2 pts) Cohen-Sutherland clipping (13_1)

1. Clips faces fast by doing concave faces properly.
2. Clips faces fast by normalizing the projection first.
3. Clips lines fast by eliminating many simple cases quickly.
4. Clips lines fast by using the fact the current CPUs do division fast.
5. Clips textures fast with a mipmap.
17. (2 pts) View normalization (13_1)

1. Makes the clip region into a cube but changes object cubes into parallelepipeds.
2. Preserves angles and distances.
3. Preserves angles but not distances.
4. Preserves distances but not angles.
5. Was obsoleted by fast CPUs.
18. (2 pts) About polygon clipping: (13_2)

1. A polygon might gain vertices.
2. A polygon might gain area.
3. If a polygon's vertices are all outside the clip region, then it may be deleted.
4. Using a 6-stage pipeline keeps the latency the same.
5. Concave polygons become convex.
19. (2 pts) From his profits from SGI, Netscape, and other startups, Jim Clark bought the world's XXX largest yacht.

1. 1st
2. 2nd
3. 3rd
4. 4th
5. 5th
20. (2 pts) Which hidden surface algorithm sorts objects back-to-front? (13_2)

1. BSP tree
2. depth (Z) buffer
3. image space
4. painter's
5. scan line
21. (2 pts) Which hidden surface algorithm preprocesses objects into a tree so that you can change the viewpoint and then render by traversing the tree in a different order? (13_2)

1. BSP tree
2. depth (Z) buffer
3. image space
4. painter's
5. scan line
22. (2 pts) Which hidden surface algorithm might send its output straight to a display like a CRT w/o ever storing the whole image? (13_2)

1. BSP tree
2. depth (Z) buffer
3. image space
4. painter's
5. scan line
23. (2 pts) Some colors that you can see on your display cannot be printed, and vv. Why? (13_4)

1. Purple is not a pure spectral color.
2. The UV emitted by the display fades the printer paper.
3. The display and printer's gamuts don't match.
4. The printer has 4 inks but the display only 3 primaries.
5. There's no such thing as a standard display - different manufacturers have different notions of red.
24. (2 pts) What is happening in the following code that is part of a picking program that we saw (11_4):

if(i==0) gl_FragColor = c;
else if(i==1) gl_FragColor = c;
else if(i==2) gl_FragColor = c;
else if(i==3) gl_FragColor = c;
else if(i==4) gl_FragColor = c;
else if(i==5) gl_FragColor = c;
else if(i==6) gl_FragColor = c;

1. This assigns to each pixel the number that we'd like returned if the user clicks on that pixel.
2. This assigns to each pixel the true color of that polygon.
3. This keeps track of how many times the user clicked on that pixel.
4. This notes how many vertices that polygon has.
5. This notes the shininess exponent for that face.
25. (2 pts) Radiosity is better than ray tracing when the scene is all

1. diffuse objects
2. objects outside the viewing region
3. objects that are very close to the viewpoint
4. specular objects
5. very small objects
26. (2 pts) Ray tracing is better than radiosity when the scene is all

1. diffuse objects
2. objects outside the viewing region
3. objects that are very close to the viewpoint
4. specular objects
5. very small objects
27. (2 pts) Firing multiple rays through each pixel handles the problem of

1. diffuse objects
2. objects outside the viewing region
3. objects that are very close to the viewpoint
4. specular objects
5. very small objects
28. (2 pts) Consider a 2D Cartesian cubic Bezier curve with these control points: (0,0), (0,1), (1,1), (1,0). What is the point at t=0? OK to look up the formula.

1. (0,0)
2. (0,1)
3. (1,0)
4. (1/2, 3/4)
5. (1/2,1)
29. (2 pts) What is the point at t=1/2?

1. (0,0)
2. (0,1)
3. (1,0)
4. (1/2, 3/4)
5. (1/2,1)
30. (2 pts) What is the point at t=1?

1. (0,0)
2. (0,1)
3. (1,0)
4. (1/2, 3/4)
5. (1/2,1)
31. (2 pts) If you interpolate a curve through a list of control points instead of approximating a curve near the points, then what happens?

1. It will not be possible to join two curves and match the radii of curvature.
2. The calculations to compute the curve will take impossibly long.
3. The curve will stay within the convex hull of the control points.
4. The curve will swing outside the convex hull of the control points.
5. This isn't possible for curves of odd degree.
32. (2 pts) If you use quadratic Bezier curves, then what happens?

1. It will not be possible to join two curves and match the radii of curvature.
2. The calculations to compute the curve will take impossibly long.
3. The curve will stay within the convex hull of the control points.
4. The curve will swing outside the convex hull of the control points.
5. This isn't possible for curves of even degree.

(Total: 64 points.)

# CG Class 25, Mon 2018-11-26

## 1   ACM SIGSPATIAL GIS Cup 1st place

Here.

In 2016, we won 2nd. We also won 2nd in 2015.

## 2   Chapter 13 slides ctd

1. We've seen some of this.

## 3   Chapter 14

1. Curves are the next chapter of Angel. WebGL does this worse than full OpenGL. Here is a summary. Big questions:

1. What math to use?
2. How should the designer design a curve?
3. My notes on Bezier curves.
2. Partial summary:

1. To represent curves, use parametric (not explicit or implicit) equations.

2. Use connected strings or segments of low-degree curves, not one hi-degree curve.

3. If the adjacent segments match tangents and curvatures at their common joint, then the joint is invisible.

4. That requires at least cubic equations.

5. Higher degree equations are rarely used because they have bad properties such as:

1. less local control. Changing one control point of a hi-degree curve changes the whole curve. Parts of the curve distant from that point may move a lot. This makes designing a desired curve impossible.
2. numerical instability. Small changes in coefficients cause large changes in the curve, even if computations are exact.
3. roundoff error. Computations are not exact.
6. See my note on Hi Degree Polynomials.

7. One 2D cartesian parametric cubic curve segment has 8 d.f. in 2D (12 in 3D).

$x(t) = \sum_{i=0}^3 a_i t^i$,

$y(t) = \sum_{i=0}^3 b_i t^i$, for $0\le t\le1$.

8. Requiring the graphic designer to enter those coefficients would be unpopular, so other APIs are common.

9. Most common is the Bezier formulation, where the segment is specified by 4 control points, which also total 8 d.f.: P0, P1, P2, and P3.

10. The generated curve starts at P0, goes near P1 and P2, and ends at P3.

11. The curve stays inside the control polygon, the convex hull of the control points. A flatter control polygon means a flatter curve. Designers like this.

12. A choice not taken would be to have the generated curve also go thru P2 and P3. That's called a Catmull-Rom-Oberhauser curve. However that would force the curve to go outside the control polygon by a nonintuitive amount. That is considered undesirable.

13. Instead of 4 control points, a parametric cubic curve can also be specified by a starting point and tangent, and an ending point and tangent. That also has 8 d.f. It's called a Hermite curve.

14. The three methods (polynomial, Bezier, Hermite) are easily interconvertible.

15. Remember that we're using connected strings or segments of cubic curves, and if the adjacent segments match tangents and curvatures at their common joint, then the joint is invisible.

16. Matching tangents (called $G^1$ or geometric continuity) is sufficient, and is weaker than matching the 1st derivative ($C^1$ or parametric continuity), since the 1st derivative has a direction (tangent) and a length. Most people do $C^1$ because it's easier and good enough. However $G^1$ gives you another degree of freedom to use in your design.

17. Similarly, matching the radius of curvature ($G^2$ or geometric continuity) is weaker than matching the 2nd derivative ($C^2$ or parametric continuity), but most people do parametric continuity.

18. Parametric continuity reduces each successive segment from 8 d.f. down to 2 d.f.

19. This is called a B-spline.

20. From a sequence of control points we generate a B-spline curve that is piecewise cubic and goes near, but probably not thru, any control point (except perhaps the ends).

21. Moving one control point moves the adjacent few spline pieces. That is called local control. Designers like it.

22. One spline segment can be replaced by two spline segments that, together, exactly draw the same curve. However they, together, have more control points for the graphic designer to move individually. So now the designer can edit smaller pieces of the total spline.

23. Extending this from 2D to 3D curves is obvious.

24. Extending to homogeneous coordinates is obvious. Increasing a control point's weight attracts the nearby part of the spline. This is called a rational spline.

25. Making two control points coincide means that the curvature will not be continuous at the adjacent joint.

Making three control points coincide means that the tangent will not be continuous at the adjacent joint.

Making four control points coincide means that the curve will not be continuous at the adjacent joint.

Doing this is called making the curve (actually the knot sequence) Non-uniform. (The knots are the values of the parameter for the joints.)

26. Putting all this together gives a non-uniform rational B-spline, or a NURBS.

27. A B-spline surface is a grid of patches, each a bi-cubic parametric polynomial.

28. Each patch is controlled by a 4x4 grid of control points.

29. When adjacent patches match tangents and curvatures, the joint edge is invisible.

30. The surface math is an obvious extension of the curve math.

1. $x(u,v) = \sum_{i=0}^3\sum_{j=0}^3 a_{ij} u^i v^j$
2. $y, z$ are similar.
3. One patch has 48 d.f. for Cartesian points, or 64 d.f. for homogeneous points, although most of those are used to establish continuity with adjacent patches.
3. My extra enrichment info on Splines.

4. The program I showed earlier is robotArm is Chapter 9.

5. To run program figure there, you may first need to fix an error in figure.html. Change InitShaders to initShaders.

Many of the textbook programs have errors that prevent them from running. You can see them in the console log.

## 4   Chapter 14 slides

1. 14_1 Curves and surfaces.
2. Programs drawing the Utah teapot.

# CG Class 24, Mon 2018-11-19

## 1   Thanksgiving trivia questions

1. When the native American Squanto greeted the Pilgrims in March 1621, what language did he use?
2. Where had he learned it?

## 2   Nice site on visualizing quaternions

Lessons by Grant Sanderson, Technology by Ben Eater.

here

## 3   Chapter 13 slides ctd

1. 13_2 Polygon rendering. Includes clipping polygons, hidden surface algorithms.
2. 13_3 Rasterization.

## 4   My commentaries

### 4.1   Clipping

1. Many of these algorithms were developed for HW w/o floating point, where even integer multiplication was expensive.
2. Efficiency is now less important in most cases (unless you're implementing in HW).
3. The idea of clipping with a 6-stage pipeline is important.
4. Jim Clark, a prof at Stanford, made a 12-stage pipeline using 12 copies of the same chip, and then left Stanford to found SGI.
1. Later he bankrolled Netscape and 2 other companies.
2. More recently he had the world's 4th largest yacht.

### 4.2   Polygon rendering

1. My note on Bresenham Line and Circle Drawing. Jack Bresenham, then at IBM invented these very fast ways to draw lines and circles with only integer addition and subtraction. My note gives step-by-step derivations by transforming slow and clear programs to fast and obscure programs.
2. My note on Two polygon filling algorithms.

### 4.3   Visibility methods

Here's my summary of problems with the main methods:

1. Painters:
1. The painter's algorithm is tricky when faces are close in Z.
2. Sorting the faces is hard and maybe impossible. Then you must split some faces.
3. However sometimes some objects are always in front of some other objects. Then you can render the background before the foreground.
2. Z-buffer:
1. Subpixel objects randomly appear and disappear (aliasing).
2. Artifacts occur when objects are closer than their Z-extent across one pixel.
3. This happens on the edge where two faces meet.
3. BSP tree:
1. In 3D, many faces must be split to build the tree.
4. The scanline algorithm can feed data straight to the video D/A. That was popular decades ago before frame buffers existed. It became popular again when frame buffers are the slowest part of the pipeline.
5. A real implementation, with a moving foreground and fixed background, might combine techniques.
6. References: wikipedia.

## 5   Textbook programs

1. Chapter 10 Mandlebrot showing serious computation in the fragment shader.