Solutions to Computer Graphics Exam 970113

Institutionen för teknisk databehandling, Bo Nordin (bosse@cb.uu.se, 018-183470), 970120

Suggested solutions to
Examination, Computer Graphics MN1/DV1 970113

1. Datorgrafik vs. bildanalys / Computer Graphics vs. Image Analysis (2p)

Simply put, computer graphics is the process of creating images from data while image analysis creates data from images. In computer graphics we create synthetic images and in image analysis we analyse images.

2. Om menyinteraktion / About Menu Interaction (3p)

Assume that the menu body is stored in a canvas.

Highlight the menu header in the menu bar.
Calculate the extent of the menu to be displayed.
Save the current pixels where the menu will be shown in a temporary canvas.
Copy the menu canvas to the screen.
Wait for button selection event.
Copy the temporary canvas to the screen (restore).
Get the mouse position and calculate the menu choice.

3. Specialprocessorer vs. generella processorer /
Special-purpose vs. general-purpose processors

Transformation, scan conversion, and display are good candidates for special-purpose processors while generation and database traversal should be done in the host processor for maximum flexibility. If interactive manipulations are rare traversal can be done in hardware as well.

4. Hårdvara / Hardware (0.5 + 0.5 + 0.5 + 0.5 = 2p)

a) # of times per time unit the image is redrawn

b) in CRTs: time from removal of excitation to the moment when the phosphorence has decayed to 10 percent of the initial light o

c) in CRTs: a metal plate with a lot of holes mounted close to the viewing surface that makes sure that each of the 3 electron beams can hit only one type of phosphor spot (R, G, or B)

d) a mouse is a relative device, a digitizer is an absolute device

5. 2D-transformationer / 2D Transformations (1 + 3 = 4p)

a) Assuming that the rotation is about (x,y) the three steps are:

translation from (x,y) to (0,0): T(-x,-y)
the rotation
translation from (0,0) to (x,y): T(x,y)

b) T(-3,-4):

1 0 -3
0 1 -4
0 0 1

R(-90):

0 1 0
-1 0 1
0 0 1

T(3,4):

1 0 -3
0 1 -4
0 0 1

The complete transformation: T(3,4) R(-90) T(-3,-4) P

where P is the column vector

x
y

6. Färgmodeller / Colour Models (1 + 1 + 2 = 4p )

   C   1   R
   M = 1 - G
   Y   1   B

b) Intensity

c) The problem of having fewer levels than 2²⁴ is solved by using a look-up table (LUT). If 8 bits are available 2⁸ = 256 colours can be displayed simultaneously: the LUT has 256 entries, each entry consists of a red, green, and blue 8-bit value. Because all that is necessary to change the image is to change the entries in the LUT, dynamic changes are possible. If the values written are actual RGB values (as on 24-bit workstations) the image must be rewritten which is a much slower operation.

7. Motif (2p)

In X, the event handling becomes a large switch where every event that the programmer wants to handle must be taken care of.

In Motif, the programmer defines functions to be called as a result occurring of events and the system takes care of the dispatching of events to the correct function.

8. Borttagning av skymda ytor / Visible Surface Determination (1 + 3 = 4p)

a) backface culling: the elimination of back-facing (surface normal points away from the observer) polygons.

bounding-box testing: checking extents in z, y, and z in order to trivially accept/reject polygons and/or determine whether two polygons overlap.

b) Warnock's algorithm successively subdivides each area into four equal squares. At each stage in the process, the projetion of each polygon has one of four relationships to the area of interest (see Foley et al, figure 13.23, page 469):

surrounding polygons completely contain the area.
intersecting polygons intersect the area.
contained polygons are completely inside the area
disjoint polygons are completely outside the area.

In four cases, no further subdivision is necessary:

All polyons are disjoint.
There is only one intersecting or one contained polyogn.
There is a single surrounding polygon
More than one polygon is intersecting, contained, or surrounding but one is a surrounding polygon that is in front of all the other polygons.

The process continues down to pixel resolution if necessary.

9. Att fylla polygoner / Filling Polygons (4p)

All edges are initially stored in the ET sorted according to their minimum y value. Within each y, edges are bucket sorted according to their minimum x value. The algorithm then loops over y, moving edges from ET to AET, and the bucket is updated (resorted) and the x coordinate for each edge is incrementally recalculated.

At each y: loop over edges, using the odd-parity rule (start with parity even, toggle parity when an edge is encountered)to determine whether we are inside (odd) or outside (even).

Horizontal edges are simply ignored.

Shared vertices are handled by counting the y_min vertex of an edge in the parity calculation but not the y_max vertex.

10. 3D-grafik / 3D viewing (2 + 2 + 1 = 5p)

a) First we need a view plane (projection plane) which is defined by a view reference point (the VRP) and a normal to the plane: the VPN (view-plane normal). In order to define a window in the VRC we need two more axes in VRC: the view-up vector (VUP) which determines the tilt of the camera, and a third axis which is defined such that the three axes together form a right-handed coordinate system.

b) The view position is defined in the VRC system. In perspective projections a position is defined: the projection reference point (PRP). In parallel projection the direction of projection (DOP) is calculated from the PRP to the centre of the window.

c) Front and back clipping planes.

11. Om fraktaler / About Fractals (1 + 1 + 1 = 3p)

a) Using Euclidean geometry involves solving equations while fractals are calculated using recursive (often infinite) procedures.

b) The fractal dimension D: ln(n) / ln(1/s) where n is the number of subparts and s is the scale factor.

c) In order to make fractal images look natural some kind of randomness is introduced. One example is the midpoint displacement algorithm.

12. Skuggning / Shading (1 + 2 = 3p)

a) Constant shading applies an illumination model once for each polygon, i.e. a single intensity value is used for all pixels in the polygon. Interpolated shading linearly interpolates the shading over each polygon from values determined at the vertices.

Constant shading produces a correct image if:

the light source is at infinity.
the viewer is at infinity.
the polygon representation is not an approximation of a curved surface.

b) Both Gouraud and Phong shading calculate the normals at vertices and then interpolates the intensity in the polygon. The difference is that Gouraud calculates the intensity at the vertices and then interpolates the intensity. In contrast, Phong interpolates the normals and then calculates the intensity.

13. Rymduppdelningstekniker / Spatial-Partitioning Techniques (1 + 1 = 2p)

a) A voxel is a rectangular cell/volume in space, a cuberille is a cube in space. In other words, a cuberille is a special case of a voxel.

b) A quadtree (2D octree) attempts to solve the memory requirements of a pixel representation by recursively subdividing the image in both dimensions, each subdivision resulting in four equal-sized subimages. The subdivision stops when a subimage is empty. In other words, only areas with image information must be stored at full resolution while empty areas take a lot less space.

Suggested solutions toExamination, Computer Graphics MN1/DV1 970113