Lect 1 Raster Displays and Algorithms

Question 1

1. What areas are included in computer graphics?

Answer 1

Graphics areas include:

• modelling, rendering, animation, user interaction, virtual and augmented reality, visualisation, (some) image processing, 3D scanning.

• Major applications include:

• games, cartoons, special effects, CAD/CAM, simulation, medical imaging, information visualization.

Question 2

2. Name the 6 major elements to a graphics system.

Answer 2

1. Input devices (mouse etc)

**2. Central Processing Unit (CPU) **

**3. Graphics Processing Unit (GPU) **

4. Memory

5. Frame buffer (Writes to the screen)

6. Output devices (Screen)

Question 3

3. Describe the graphics pipline. What are the 5 key stages?

Answer 3

**1. 3D MODEL: **Start off with 3D model

2 Model View Transformation:

• Map from the WCS(World coordinate system) to the CCS(Camera Coordinate System)
• Culling and lighting

3 Projection:

• Map from CCS to Screen CS
• Clipping(Clip any fragments not in view)
• Persp. division

4 Rasterization:

• colour
• Visibility

5: Display:

• Framebuffer Display

Question 4

4. What are 3D geometric models?

Answer 4

• These models describe 3D objects using mathematical primitives, e.g. spheres, cubes, cones and polygons.
• The most common type is a triangle mesh composed of triangles with shared vertices.

Question 5

5. Explain what transforms are.

Answer 5

• Transforms refers to the task of converting 3D spatial coordinates to a 2D view for rendering.
• 3 basic tranforms. Translate, rotate and scale.
• Work on whole objects rather than individual vertices.
• Transforms are represented as matrices.
• They set up coordinate systems.

Question 6

6. Describe the WCS.

Answer 6

World Coordinate System (WCS) - Also known as the universe or global or sometimes model coordinate system.

This is the base reference system for the overall model, ( generally in 3D ), to which all other model coordinates relate.

• A coordinate system is an origin and also the direction of the axes
• We need coordinate systems for vectors and transforms to make sense

Question 7

7. What is an Object Coordinate System?

Answer 7

An object in a scene needs to have a point of origin and an orientation set by the x,y,z axes.

Vertices defined relative to the specific object (in local coordinate space)

The object position changes relative to the world, so its vertices should follow

Sometimes objects in a scene are arranged in a hierarchy, so that the “position” of one object in the hierarchy is relative to its parent in the hierarchy scheme, rather than to the world coordinate system.
E.g., a hand may be positioned relative to an arm, and the arm relative to the torso.

This allows for grouped transformations

Question 8

8. Desrcribe the Viewpoint Coordinate System.

Answer 8

• Also known as the camera coordinate system.
• This coordinate system is based upon the viewpoint of the observer, and changes as they change their view.
• Moving an object “forward” in this coordinate system moves it along the direction that the viewer happens to be looking at the time.

Question 9

9. What is a screen coordinate system?

Answer 9

• This 2D coordinate system refers to the physical coordinates of the pixels on the computer screen, based on current screen resolution.

( E.g. 1024x768 )

Question 10

10. Describe a raster display.

Answer 10

• The basic rendering procedure is a list of polygons and vertices that produces an image of the object they represent.
• This image is an array, or raster, of picture elements (pixels).
• The raster is organised into rows and each row holds a number of pixels.
• The quality of an image is related to the accuracy of the pixel colour value and the number of pixels in the raster.

Question 11

11. How do you reference a Pixel?

Answer 11

• Displays usually index pixels in an ordered pair (x, y) indicating the row and column number of the pixels.

• If a display has nx and ny rows of pixels, the bottom left pixel is (0,0) and the top-right is (nx-1, ny -1).
• (In some cases the top left pixel has the coordinates (0,0) as it is the convention for television transmission.)

Question 12

12. Describe RGB colour?

Answer 12

• The colour of a pixel is usually recorded as three values: red, green and blue (RGB).
• Mixing these three primary lights is sufficient to give the impression that a full rainbow spectrum is reproducible.
• This is additive colour mixing (it differs from the more familiar subtractive colour mixing for paints where red, yellow and blue are the primaries).

Question 13

13. Describe the RGB colour Model.

Answer 13

• A colour in the RGB colour model is described by indicating how much of each of the red, green, and blue is included.
• The colour is expressed as an RGB triplet (r,g,b), each component of which can vary from zero to a defined maximum value.
• If all the components are at zero the result is black; if all are at maximum, the result is the brightest representable white.
• Human cones from the eye roughly corespond with the RGB colour model.

Question 14

14. Give examples of RGB colour mixing.

Answer 14

red(1,0,0)+green(0,1,0) =yellow(1,1,0)

green (0, 1, 0) + blue (0, 0, 1) = cyan (0, 1, 1)

blue (0, 0, 1) + red (1, 0, 0) = magenta (1, 0, 1)

red(1,0,0)+green(0,1,0)+blue(0,0,1) =white(1,1,1)

Question 15

15. Explain 24 bit colour.

Answer 15

• Actual RGB levels are specified with an integer for each component.
• This is most commonly a one byte integer, so each of the three RGB components is an integer between 0 and 255.
• The three integers together take up three bytes, which is 24 bits, thus a system with 24 bit colour has 256 possible levels for each of the three primary colours.

Question 16

16. Describe the Rasterization process.

Answer 16

• Converting 3D information for display on a 2D screen involves a process known as rasterization.
• Rasterization algorithms takes a 3D scene, described as polygons/mesh/wireframe, and renders it as discrete 2D primitives.

Question 17

17. Describe how lines are drawn to screen.

Answer 17

• Line drawing involves taking two endpoints in screen co-ordinates and drawing a line between them.
• For general screen co-ordinates (x0 , y0) and (x1 , y1) the algorithm should draw a set of pixels that approximates a line between them.
• Need to use algorithms to work out the nearest pixels to a uniform line.

Question 18

18. Name 2 line drawing algorithms.

Answer 18

• Commonly used procedures are the Bresenham algorithm and the midpoint algorithm (these differ slightly in their methods but produce the same lines).
• Line drawing needs to be fast and as simple as possible, giving a continuous appearance.

Question 19

19. Describe the **Bresenham Algorithm. **

Answer 19

• The algorithm works incrementally from a starting point (x0 , y0) and the first step is to identify in which one of 8 octants the direction of the end point lies.
• The line is drawn by stepping one horizontal pixel at a time from x0 to x1 and at each step making the decision whether or not to step +1 pixel in the y direction.
• Scaled to work with integers making it very fast.

Question 20

20. What is the decision we need to make when looking at Bresenhams algorithm?

Answer 20

• Since the point on the line may not be in the centre of the pixel we must find the second best point - the one where the distance from the line is the smallest possible.
• Decision: do we draw (x+1, y) or do we draw (x+1, y+1)?
• d1 is smaller than d2 so the next point after (x, y) that should be drawn is (x+1, y+1).

Question 21

21. Describe the **Midpoint circle **algorithm.

Answer 21

• The algorithm starts with the circle equation x² + y² = r².
• The midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle.
• More computationaly expensive than a simple line.
• We can work out one octant and then reflect this to give 1/4 circle and carry on using this simple reflection method to acheive a full circle.

Question 22

22. How is a wireframe made more realistic?

Answer 22

• When you want to make a wireframe more realistic you need to take away the edges you cannot see, i.e. you need to make use of hidden line and hidden surface algorithms.
• The facets in a model determine what is and what is not visible.

Question 23

23. Describe Hidden Surface Drawing.

Answer 23

• In a wireframe drawing, all the edges of the polygons making up the model are drawn.
• A hidden surface drawing procedure attempts to colour in the drawing so that joins between polygons and polygons that are out of sight (hidden by others) are not shown.
• E.g. if you look at a solid cube you can only see three of its facets at any one time, or from any one viewpoint.
• To construct a hidden surface view, each polygon is projected onto the viewing plane. Instead of drawing the edges, pixels lying inside the boundary formed by the projected edges of a polygon are given an appropriate colour.
• This is not a trivial task. Any procedure to implement the filling task must be very efficient.

Question 24

24. Describe recursive seed fill.

Answer 24

• Simple but slow.
• A pixel lying within the region to be filled is taken as a seed, set to record the chosen colour.
• The seed’s nearest neighbours are found and, with each in turn, this procedure is carried out recursively.
• The process continues until the boundary is reached.

Question 25

25. Describe **ordered seed fill**.

Answer 25

* A **seed pixel** is chosen inside the region to be filled. * Each pixel on that row, to the left and right of the seed, is filled pixel by pixel until a boundary is encountered. * Extra seeds are placed on the rows above and below and are processed in the same manner. * This is also recursive but the number of recursive calls is dramatically reduced.

Question 26

26. Describe a useful algorithm for filling polygons.

Answer 26

**Scanline fill:** * The polygon is filled by stroking across each row and colouring any pixels on that row if they lie within the polygon. * This is the most useful filling procedure for a 3D polygon as it works very efficiently for simple convex shapes.

Question 27

27. Give detailed steps on how to use the **Scanline Fill Algorithm. **

Answer 27

* remove any horizontal edges from the polygons * find the max and min y values of all polygon edges. * make a list of scanlines that intersect the polygon for each scanline repeat * for each polygon edge list the pixels where the edge intersects the scan line * order them in ascending x value (p0, p1, p2, p3) * step along the scanline filling pairwise (p0→p1, p2→p3) If the intersection is the ymin of the edge’s endpoint, count it. Otherwise, don’t.

Question 28

28. What is the simplest of all **hidden surface algorithms**?

Answer 28

**The Painter’s Algorithm** ## Footnote * Simplest of all the hidden surface rendering techniques. * **Not ‘true’ hidden surface** as it can’t handle polygons which intersect or overlap in certain ways. * Relies on the observation that if you paint on a surface, you paint over anything that had previously been there, thus hiding it, i.e paint from furthest to nearest polygons.

Question 29

29. Name the steps of the **Painters Algorithm. **

Answer 29

1. sort the list of polygons so that it is ordered by distance from the viewpoint with the polygon furthest away being at the start of the list 2. repeat the following for all polygons in the ordered list: 3. draw projected polygon Image below shows overlapping polygons.. these can make the algorithm fail!

Question 30

30. Describe the **Z-buffer algorithm.**

Answer 30

* It is very impractical to carry out a depth sort among every polygon for every pixel. * The basic idea of the **z-buffer** algorithm is to test the **z-depth** of each surface to determine the closest (visible) surface. * The **z-buffer** stores values [0 .. ZMAX] corresponding to depth of each surface. * If the new surface is closer than one in the buffers, it will replace the buffered values

Question 31

31. How does the **Z-buffer** algorithm work? Give pseudo code.

Answer 31

Declare an array **z\_buffer(x, y)** with one entry for each pixel position. Initialize the array to the maximum depth. ## Footnote **for each polygon P** **for each pixel (x, y) in P** compute z\_depth at x, y **if z\_depth \< z\_buffer (x, y) then** set\_pixel (x, y, color) z\_buffer (x, y)

Question 32

32. How does a disply show only what is visible to a camera?

Answer 32

Using clipping and culling. ## Footnote * We want to restrict polygons to what will appear within the field of view. * The default **clipping rectangle** is the full canvas ( the screen ), and it is obvious that we cannot see any graphics primitives outside the screen.

Question 33

33. Explain **Culling.**

Answer 33

• **Culling** refers to discarding any complete polygons that lie outside the clip rectangle. So: • Remove polygons behind the **projection plane** • Remove polygons projected to lie outside the** clip rectangle** • Cull any **backfaces** (any polygon that faces away from the viewpoint)

Question 34

34. What should be considered for **clipping**?

Answer 34

* To clip a line we only need to consider its **endpoints.** If both endpoints of a line lie inside the clip rectangle, the entire line lies inside the clip rectangle – no clipping required. * If one **endpoint** lies inside and one outside we must compute the **intersection** point. * If both endpoints are outside the **clip rectangle**, the line may or may not intersect with the clip rectangle.

Question 35

35. Describe the **Cohen-Sutherland Algorithm. **

Answer 35

• The **Cohen-Sutherland algorithm** uses a divide-and-conquer strategy. • The line segment's endpoints are tested to see if the line can be **trivially accepted or rejected**. If the line cannot be trivially accepted or rejected, an intersection of the line with a window edge is determined and the trivial reject/accept test is repeated. • This process is continued until the line is accepted.

Question 36

36. How does the **Cohen-Sutherland algorithm** determine if endpoints are inside or outside a **window**?

Answer 36

* To determine whether endpoints are inside or outside a window, the algorithm sets up a **half-space code** for each endpoint. * Each edge of the window defines an infinite line that divides the whole space into two half-spaces, the **inside half-space** and the **outside half-space**, as shown below. * As you proceed around the window nine regions are created - the eight outside regions and the one inside region. * Each of the nine regions associated with the window is assigned a **4-bit code** to identify the region.

Question 37

37. Explain how **Cohen-Sutherland's algorithm** reads the codes' bits.

Answer 37

* The sequence for reading the codes' bits is **LRBT** (Left, Right, Bottom, Top). * For any endpoint(x,y)of a line, the code can be determined that identifies the region in which the endpoint lies. The code's bits are set according to the conditions seen below:

Question 38

38. Explain how the logical **AND** is used in **Cohen-Sutherlands algorithm.**

Answer 38

* Once the codes for each endpoint of a line are determined, the logical **AND** operation of the codes determines if the line is completely outside of the window. If the logical **AND** of the endpoint codes is not zero, the line can be trivially rejected. * E.g. if an endpoint had a code of 1001 and the other endpoint had a code of 1010, the logical **AND** would be 1000 indicating the line segment lies outside of the window. If endpoints had codes of 1001 and 0110, the logical **AND** would be 0000, and the line could not be trivially rejected.

Question 39

39. Explain how the logical **OR** is used in **Cohen-Sutherlands algorithm.**

Answer 39

* The logical **OR** of the endpoint codes determines if the line is completely inside the window. If the logical **OR** is zero, the line can be trivally accepted. * E.g. if the endpoint codes are 0000 and 0000, the logical **OR** is 0000 - the line can be trivally accepted. If the endpoint codes are 0000 and 0110, the logical **OR** is 0110 and the line can not be trivally accepted.