Computer Science 455
Instructor: R. P. Burton
Second Quiz
October 7-8, 2002

Name _________________________________________	Score ____________/59

1.The primary advantage of the Bresenham line algorithm, relative to the DDA algorithm is
a.it is universally faster
b.it is faster for all but short lines
c.it handles lines in virtually any orientation
d.there is no accumulating round-off error

(b)

2.Suppose time t is required to load (determine the memory location of) the first point of a DDA or Bresenham line into the frame buffer.  In an efficient environment, approximately how much time is taken to load the second point of the same line.
a.very nearly the same amount of time
b.less time
c.sometimes less time, sometimes more time; no general statement can be made

(b)

3.Which is likely to produce the more uniform circle?
a.the implicit equation of a circle solved for y (or x).
b.the polar form of a circle
c.both (a) and (b) produce equivalently uniform circles, but neither is very efficient

(b)

4.What is/are the disadvantages of a circle-generating DDA algorithm?
a.it produces either a circle which does not close or an ellipse
b.it produces a nonuniform circle
c.it uses time-consuming operations

(a)

5.Suppose you have computed one point on a circle.  Typically, how many other points on the circle can be determined simply by changing signs and swapping variables?
a.none
b.1
c.3
d.7
e.15

(d)

6.The initial decision parameter for the Bresenham circle algorithm is 5/4 – r.  What does the 5/4 represent?
a.the aspect ratio of a typical display
b.the frequency with which the decision parameter changes signs
c.the tangent at the first pixel to the right of (0,r)
d.(none of the above)

(d)

7.The Bresenham ellipse algorithm 
a.is limited to unrotated ellipses centered about the origin
b.is limited to unrotated ellipses
c.is limited to ellipses centered about the origin
d.is adaptable to ellipses in any position and orientation in the 2D plane

(d)

8.Which is likely to produce more accurate lines?
a.grid intersections at pixel centers
b.grid intersections are the corners of pixel bounding boxes.
c.Neither (a) nor (b) is more accurate.

(b)

9.Which is preferable for geometric shapes?
a.pixel centers as close as possible to boundaries
b.pixels interior to, but as close as possible to boundaries
c.Neither (a) nor (b) is preferable.

(b)

10.For the scan-line polygon fill algorithm, how many scan-line intersections are generated by a scan line that passes through a vertex?
a.none
b.one
c.two
d.one or two, depending on the vertex’s neighbors
e.scan lines must not be allowed to pass through vertices

(d)

11.On what basis are the edges in a sorted-edge table sorted?
a.clockwise (or counterclockwise) around the polygon
b.on increasing x (of the leftmost endpoint), and then with longer edges before shorter edges
c.on increasing x, and then with shorter edges before longer edges
d.on increasing y, and then with longer edges before shorter edges
e.on increasing y, and then with shorter edges before longer edges

(e)

12.Given a polygon of n edges, what is the maximum number of edges than can be in the (properly organized) active edge list at any point in time?  What is the minimum number?.
a.(n,0)
b.(n-1, 0)
c.(n-1, 1)
d.(n,1)

(b)

13.A line is drawn from a point P to another point exterior to a very complicated polygon.  The line crosses 365 edges.  What can you say about the point P?
a.It is interior to the polygon
b.It is exterior to the polygon
c.It could be either interior or exterior to the polygon, depending on whether or not the polygon is self-intersecting.

(a)

14.A line is drawn from a point S at the center of a polygon to another point exterior to the polygon.  This line encounters exactly two polygon edges crossing it from the right to left, and no polygon  edges crossing it from the left to right as the line proceeds toward the point exterior to the polygon.  What can you conclude?
a.The polygon is not closed.
b.The polygon is concave.
c.Something is awry; this is an impossible situation.
d.The point S is exterior to the polygon.

(d – draw a 5-pointed star)

15.Suppose the boundary-fill algorithm is used efficiently to fill a polygon which can be enclosed tightly in a rectangle measuring  200 pixels by 200 pixels.  The polygon has a hole in the middle which can be enclosed in a rectangle measuring 30 pixels by 40 pixels.  How large is the stack (used to fill the polygon) likely to get?
a.not more than 200 entries
b.more than 200, but not more than 1000 entries
c.more than 1000, but not more than 4000 entries
d.substantially more than 4000 entries

(a)

16.The boundary of a polygon to be boundary-filled is 8-connected.  The polygon can be enclosed tightly in a rectangle measuring 200 pixels by 200 pixels.  An 8-connected fill is used.  What is the maximum number of pixels that can be painted?
a.not more than 200 
b.more than 200, but not more than 1000 
c.more than 1000, but not more than 4000 
d.substantially more than 4000 

(d)

17.A green polygon, all alone on a black background, is to be painted blue using a flood-fill algorithm.  What color should the boundary of the green polygon be?
a.green (i.e. it doesn’t need a separately painted boundary)
b.anything but green
c.anything but blue 
(a)

18.Which of the following is a necessary activity if an area is to be “tiled” with a rectangular pattern?
a.the tiles must align with the area boundary and the area to be filled must be an integer multiple of the tile’s size
b.the tiles must be smaller than the area to be filled
c.the tile must be larger than the area to be filled
d.the specification of the corner of a “first” tile must be within the area to be filled
e.the tile must not contain a color of the area to be filled
f.(none of the above are necessary)

(f)

19.By tradition, a bit map for a character T_large, which is three times the size of a character T_small, is exactly a 3x magnification of the bit map for T_small.  (“small” and “large” have nothing to do with upper or lower case)
a.true
b.false

(b)

20.All of the following can have “attributes” except
a.points
b.lines
c.curves
d.characters
e.(no exceptions in this list)

(e)

21.A horizontal line consists of 1000 pixels and has length L.  A 45 degree line of 1000 pixels has length
a.Sqrt(l)
b.L/sqrt(2)
c.L
d.L * sqrt(2)

(c)

22.Computer displays do not display either true points or true lines or anything else with less than 2 dimensions.  In these cases they display only small or narrow areas.
a.true
b.false

(a)

23.What is the most efficient way to display a brush stroke with “gaps” internal to the stroke?
a.Treat the stroke as a polygon and fill it with a pattern after the polygonal boundaries are determined.
b.Treat the stoke as a polygon and randomly set some of the pixels internal to the polygon.
c.Write the pattern pixels (internal to the stroke) to the frame buffer only after the elapse of times t as the stroke is being generated or only after the stroke device has moved distances d as the stroke is being generated.

(c)

24.The frame buffer measures 1024 x 1024.  It can display 256 colors from a palette of 4,096.  Approximately how much memory is saved over a frame buffer of the same size which can display any of 4,096 colors?
a.none
b.a third
c.half
d.roughly 90%

(b – 8 bits x 1024 x 1024 + 12 bits x 256 vs. 12 bits x 1024 x 1024)

25.A display device which consists of pixels which are either on (white) or off (black) presents images which appear to contain only black or white – no grays.
a.true
b.false

(b)

26.What is “soft fill?”
a.mixing background and foreground (polygon) colors
b.blurring of polygon boundaries to achieve antialiasing
c.blurring of polygon boundaries to achieve fuzziness
d.approximating polygon boundaries to achieve efficiency

(a)

27.Kerning
a.is an art which defies automation
b.has been automated

(b)

28.What is the purpose of bundling attributes?
a.to ensure their compatibility
b.to be able to specify (possibly large) collections of attributes with a single command
c.to say how attributes should be interpreted on each output device

(c)

29.What is the most significant use of inquiry functions?
a.the learn how attributes were set by someone else to achieve a particular look that we may wish to duplicate
b.to facilitate temporary changes in attributes
c.to verify that attributes have been set in accordance with our wishes

(b)

30.For the purposes of antialiasing, treating the screen as it if were covered with a finer grid is called
a.supersampling
b.area sampling
c.pixel phasing

(a)

31.Micropositioning of the electron beam is called 
a.supersampling
b.area sampling
c.pixel phasing
d.nonsense, because pixels are at fixed positions

(c)

32.An antialiased boundary between a red polygon and a blue polygon probably is
a.made of pixels which are either red or blue (but not both), depending on which polygon has achieved pixel dominance
b.fuzzy or blurry in its appearance
c.purple or magenta or something like that, but you’ll see it as a crisp boundary

(c)

33.Which line drawing algorithm is most easily adapted for antialiasing?
a.simple DDA
b.symmetric DDA
c.Binary Rate Multiplier
d.Bresenham
e.(none of the above can be adapted; all require a postprocessing pass)

(d)

34.When scaling of a polygon occurs relative to a point other than the origin,
a.the distance of the polygon from to the origin is changed for points external to the polygon.
b.the polygon itself is scaled
c.both (a) and (b) occur

(c)

35.When a polygon is rotated about a point other than the origin
a.the distance of the polygon from the origin changes in proportion to the angle of rotation
b.the orientation of the polygon changes
c.both (a) and (b)

(b)

36.A 2x2 matrix is sufficient for representing all of the following basic transformations EXCEPT
a.translation
b.scaling
c.rotation
d.(no exceptions here)

(a)

37.How many points in homogeneous coordinate space correspond to the two-dimensional point (3,5)?
a.just 1
b.exactly two
c.four
d.lots and lots

(d)

38.The idea of (1) translating so a pivot point is at the origin, (2) rotating about the origin, and (3) translating so the pivot point is back in its original position describes
a.The intermediate steps a polygon actually goes through as it is rotated about an arbitrary pivot point
b.the derivation of a transformation to rotate about an arbitrary pivot point
c.both (a) and (b)

(b)

39.Suppose a composite transformation consists of basic transformations T1, T2, T3, T4, and T5.  Suppose we wish to find the inverse of the composite transformation.  All of the following are acceptable except
a.Provide the inverses of basic transformations T1…T5 and compose them in that order
b.Provide the inverses of basic transformations T1…T5 and compose them in reverse order
c.Invert the composite transformation using Gauss elimination.
d.(no exceptions here)

(a)

40.How many (element) multiplication operations need to be performed to compose two 3x3 matrices, each of which represents a basic transformation?
a.9
b.18
c.27
d.36
e.54

(b)

41.Reflection “across” a point is
a.unique and does not require specification of the orientation of reflection axes
b.ambiguous and requires the specification of the orientation of the reflection axes
c.ambiguous and requires the specification of the position and orientation of the reflection axes

(a – run a line from each vertex to the point and continue it an equivalent distance and direction beyond the point.  This generates the reflected vertex.)

42.
| -1  0  0 | 
 	The 3x3 transformation   	|  0 –1  0 | 	does NOT represent
|  0  0  1 | 
a.a scaling transformation
b.a reflection transformation
c.a rotation transformation
d.(it represents all of the above)

(d)

43.
| 1  a  0 | 
 	The 3x3 transformation   	| b  1  0 | 	where a  b, represents
| 0  0  1 | 

a.a scaling transformation
b.a rotation transformation
c.a reflection transformation
d.a shearing transformation
e.(it does not represent any of the above)

(d)

44.When transforming the geometry of entities described relative to coordinate system A so that they are described relative to coordinate system B, first
a.find a transformation that superimposes coordinate system A on coordinate system B
b.find a transformation that superimposes coordinate system B on coordinate system A
c.consider the position, orientation, and scale(s) of the two coordinate systems, and use answer (a) for some of the basic transformations and answer (b) for others

(b)

45.One coordinate system can be mapped to another, provided that neither system is ______ relative to the other.
a.rotated 
b.scaled
c.scaled nonuniformly
d.sheared
e.reflected
f.(no exceptions here)

(f)

46.Suppose you are considering a bit-block transfer or a pixel-block transfer.  The blocks are overlapping rectangular regions of the frame buffer.  What do you do?
a.You’re out of luck if they overlap.
b.Start with a line containing a non-overlapped corner of the source rectangle.
c.Start with a line containing a non-overlapped corner of the destination rectangle.
d.Start with a line containing an overlapped corner of either the source or destination rectangles.
e.Choose (b), (c), or (d) based on the nature of the overlap.

(d)

47.In a graphics context, a _____ is a rectangular area on the display device to which a rectangular area in world coordinates is mapped.
a.viewport
b.window

(a)

48.Changes made to a viewport generally impact the contents of the viewport 
a.directly
b.inversely

(a)

49.Changes made to the window generally impact the contents of the window
a.directly
b.inversely

(b)

50The window to viewport transformation, as derived in class, involves only translation and scaling, with the translation and scaling factors remaining constant if the mins and maxes of the window and viewport do not change.
a.true
b.false

(a)

50.The mapping from a(n aligned) window in master coordinates to a window in world coordinates is mathematically the same as
a.a mapping from a window in world coordinates to a viewport in screen coordinates
b.a mapping from a window in world coordinates to a viewport in normalized device coordinates
c.a mapping from a viewport in normalized device coodinates to a viewport in physical device coordinates
d.(all of the above)
e.(none of the above)

(d)

51.The most efficient place to clip is
a.between world and screen coordinates
b.after the final mapping

(b)

52.After clipping a polygon, you should be left with
a.a collection of endpoints
b.a collection of line segments
c.a collection of polygons
where a collection may be empty, or may have one or more elements.

(c)

53.Which is attempted first by the Cohen Sutherland line-clipping algorithm?
a.trivial acceptance
b.trivial rejection
c.testing of the relationship of the line segment to the clipping region boundaries

(a)

54.Finding the intersection of a line segment with a conventional clipping region boundary typically involves
a.solving for x and y
b.solving for x or y, but not both
c.solving for neither x nor y

(b)

55.Suppose delta_x + delta_y  for a particular line segment of slope 1 is 1050.  How many midpoint subdivisions are required to find the intersection of the line segment with a conventional clipping region boundary?
a.just 1
b.more than 1, but less than 10
c.more than 10, but less than 20
d.more than 20, but less than 100
e.more than 100

(b)

56.Suppose you have produced all the p’s and q’s for line clipping using Liang and Barsky.  Which of the following can be determined from just the p’s and q’s? (be careful)
a.If a line segment is parallel to a window boundary and, if so, which side of the window boundary it is on
b.If the line segment intersects the window boundary and, if so, whether it goes from inside the boundary to outside, or vice versa.
c.The actual intersection point of the line segment and the window boundary (if it exists and assuming they are not parallel)
d.(all of the above)
e.(none of the above)

(d)

57.The Nicholl Lee Nicholl algorithm determines if a line segment from P1 to P2 intersects a window by comparing the slope of that line segment to the slope(s) of at most ___ other lines.
a.one
b.two
c.four
d.twelve

(c)

58.Nicholl Lee Nicholl exploits symmetry by reducing nine cases (the window and the eight surrounding regions) to ___ cases.
a.three
b.four
c.six

(a)

59.A polygon represented by points or line segments can be clipped using a point or line clipping algorithm, respectively.
a.true
b.false

(a)