1

Study Material

Class: III BCA A & B

Semester:V

Subject : COMPUTER GRAPHICS

Unit : IV

Unit IV

Raster Graphics

Raster graphic fundamentals

Generating a raster image – representing a raster image –scan converting line drawings –displaying characters-speed of scan conversion –natural images.

Solid area scan conversion

Geometric representations of areas- scan converting polygons –priority –the y-x algorithm-properties of scan converting algorithms.

Raster graphic system

Representations –Raster manipulation functions-system using raster representations.

Raster display hardware

Raster display devices – frame buffers-the random access frame buffer- real time scan conversion –other encoding schemes.

Raster Graphic Fundamentals:

Random scan displays:

Random scan display unit, a CRT has the electron beam directed only to the parts of the screen where a picture is to be drawn. Random scan monitors draw a picture one line at a time and for this reason are also referred to a vector displays

Raster Graphics Fundamentals

It is based on television technology. In raster scan the electron beam is swept across the screen, one row at a time from top to bottom. As the electron beam moves across each row, the beam intensity is turned on and off to create a pattern of illuminated spots. Picture definition is stored in a memory area called the refresh buffer or frame buffer in a rectangular matrix.

Applications of Raster-scan Graphics
  1. Flight simulation
  2. Animation
  3. Design
  4. Technical illustration
  5. Printing and plotting
  6. Image processing

Generating a raster image: the frame buffer display

A Raster image is generated by plotting point by point the intensity value of each pixel in a two dimensional raster or matrix of pixels. An image represented as a raster can be displayed on a CRT by means of the frame buffer display.

This device consists of three components.

  1. The frame buffer itself, a large random access memory in which the intensity of each pixel is stored as a binary intensity value.
  2. A TV monitor, on which the image is displayed.
  3. A display controller, whose purpose is to scan repeatedly through the matrix of intensity values stored in the frame buffer and to produce from them a signal

On a black and white system with one bit per pixel, the frame buffer commonly called bitmap. For systems with multiple bits per pixel, the frame buffer is often referred as pixmap.

At the end of each scan line the electron beam returns to the left side of the screen to begin displaying the next scan line. The return to the left of the screen, after refreshing each scan line is called the horizontal retrace of the electron beam. And at the end of the each frame, the electron beam returns (vertical retrace) to the top left corner of the screen to begin next frame.

On some raster systems (TV), each frame is displayed in two passes using interlaced refresh procedure. In the first pass, the beam sweeps across every other scan line. Interlacing of the scan lines in this way allows us to see the entire displayed in one- half the time it would have taken to sweep across all the lines at once from top to bottom. Interlacing is primarily used with slower refreshing rates. On an older, 30 frames per second, non-interlaced display, for instance, some flicker is noticeable. But with interlacing, each of the passes can be accomplished in 1/60th of a second, which brings the refresh rate nearer to 60 frames per second. This is an effective technique for avoiding flicker providing that adjacent scan lines contain similar display information.

Some raster system contains display processor, sometimes referred as a graphics controller or a display controller.

The purpose of the display controller is to free the CPU from graphics operations. A major task of the display processor is digitizing a picture definition given in an application program into a set of pixel intensity values for storage in the frame buffer. This digitization process is called scan conversion.

Representing a Raster Image

To produce an image on a frame buffer display, we need only provide a function for setting value of a pixel

SetPixel (raster, x, y, intensity);

Raster refers Frame buffer

To retrieve pixel values from a raster representation.

GetPixel(raster,x,y);

Raster Coordinate System

The most natural coordinate system is a 2D scheme with x increasing to the right, y increasing upward, and units chosen equal to the pixel spacing. The x and y coordinate values passed to the setpixel and getpixel functions must be converted into the address of the byte in the raster array holds the pixel value. The conversion is performed by

If the Base address represent the address of the first byte in the raster array, corresponding to the pixel in the lower left corner of the raster the address p of the pixel at (x, y)

P= Base address + (x max - xmin)(y - ymin)+(x - xmin)

Where xmin, xmax, ymin, ymax are the integer coordinates of the boundaries of the raster.

This calculation is simplified as

P= a+ by+ x

Where b= xmax-xmin and a =Baseaddress-bymin-xmin.

Scan Converting Line drawings

Directly we couldn’t display vectors on a frame buffer display, each vector must be converted from a conventional geometric representation into a raster representation using a process called scan conversion.

A small modification must be made to the DDA algorithm to adopt it to scan conversion. After computing each dot coordinate position (x, y) the algorithm plot the point, not by adding a dot to the display file but by calling SetPixel (Frame buffer, x, y, intensity), where the intensity is the shade of the line.

The simplest approach is to treat the display as the logical equivalent of a storage tube terminal. Thus we can add its content but we cannot selectively erase. The only changes to the graphics package are in the display code generator.

The two changes are

  1. The routine to clear the screen is changed to store an appropriate background value into every byte in the frame buffer.
  2. The routine to add a line call DDA routine that sets the appropriate pixels in the frame buffer.

Another approach Selective modification used for achieving better performance. To erase a individual line, for example the same DDA algorithm can be used, but each call to SetPixel will specify the intensity of the background. Although line eraser may leave holes in remaining lines, the holes can be filled by small amount of additional scan conversion.

Displaying Characters

The frame buffer can contain characters of different sizes, different typefaces and different colors. The pattern of pixels that display proper character shape could be represented as a long list of calls to SetPixel, it is more compactly described in mask raster.

The Pattern of each character inserted in the Mask raster by using the following procedure. A value 1 denotes a pixel that is part of the character shape, where as 0 indicate unaltered pixel of the character. The mask raster representation leads to a very simple algorithm for adding those characters to the frame buffer.

Procedure WriteMask (var MaskRaster : raster; x, y, intensity : integer);

Var i, j : integer;

Begin

For j = MaskRaster.ymin to MaskRaster.ymax-1 do

For i = MaskRaster.xmin to MaskRaster.xmax –1 do

If getpixel(MaskRaster,i,j)>0 then

Setpixel(framebuffer,x+i,y+i,intensity)

End

Using background color as intensity can erase characters. Various character appearances can be created from a single mask by altering the procedure for writing the characters into frame buffer.

Each character can be represented by a raster that records the color of each pixel, reserving a special transparent value to indicate pixels that should not be modified. Then the raster servers the dual purpose of specifying where the character pattern lies and what color values to use.

Procedure ColourRaster (var ColourRaster : raster; x, y, intensity : integer);

Var i, j : integer;

Begin

For j = ColourRaster.ymin to ColourRaster.ymax-1 do

For i = ColourRaster.xmin to ColourRaster.xmax –1 do

If getpixel (ColourRaster, i, j) >transparent then

Setpixel(framebuffer, x+i, y+i, Getpixel (ColourRaster, i, j)

End

Speed of Scan Conversion

For y= framebuffer.ymin to framebuffer.ymax-1 do

For x =frmaebuffer.xmin to framebuffer.xmax-1 do

Setpixel(framebuffer,x,y,Background)

Typical size of the frame buffer raster this loop will require many thousands of calls to setpixel. Each call checks coordinates and computes the frame buffer address of the pixel to be modified. These calculations are very wasteful. To provide a separate function Clear that avoids the redundant checking and replaces frame buffer values as fast as the hardware will allow. All scan conversion algorithm share a common property: they need fast access to the frame buffer memory.

Natural Images

The original light image is sampled by recording its intensity on a grid of points and then reproduced by passing these intensities to the raster display. TV images are generated in this fashion. Sampling natural images with digital measurement allows a computer to operate on the image, improve its quality, compare it with other images, store its digital representation for later retrieval.

Sampling

A pixel displayed on a raster display is not a mathematically extremely small point but emits light over a small area, roughly the size of a square of the raster grid. The intensity value of the pixel must represent the light from all sources falling on the corresponding small area of the image.

If such area sampling is not performed properly on lines and other geometric objects, edges of the object will exhibit irregular staircase patterns.

Halftoning

A natural image that has pixels of a great many different intensity values on a display with a limited range of output values. Solution to this problem is called Halftoning. The basic idea is to use patterns of back and white to give the impression of intermediate intensities.

1.Pattern technique

Take 3 X 3 pixel design the different possible patterns. Patterns must be carefully designed to avoid generating annoying textures.

Representing natural images these patterns won’t be sufficient.

2.Thresholding

If the image intensity of a pixel exceeds a threshold, white is displayed for that pixel, otherwise black. The display of white or black introduces errors in the display.

Two techniques used to overcome those errors:

Modulation

This technique modulates the intensity signal with a single M(x,y) whose value range from –g ot g with average value 0. the pixel at (x,y) is made white if I(x,y) + M(x,y)>g otherwise it is set to black.

Error distribution.

Records the error introduced by a thresholding operation and compensates for the error by distributing it to neighboring pixels. The algorithm given below selects an intensity for display at(x,y) and distributes the error to the three neighbor, three eights of the error is propagated to the right neighbor, three eights to the bottom neighbor and one fourth along the diagonal.

If I(x,y)>g then begin

Setpixel(framebuffer,x,y,1);{Make pixel white}

Error= I(x,y)-w;

End else begin

Setpixel(framebuffer,x,y,0);{Make pixel Black}

Error=I(x,y)-b;

End

I(x+1,y)=I(x+1,y)+(3*error)/8;

I(x,y-1)=I(x,y-1)+(3*error)/8;

I(x+1,y-1)=I(x+1,y-1)+error/4;

The error distribution method above is designed so that a top- to bottom left to right scan of the image to generate pixel values never requires backing up.

Solid Area Scan Conversion

Solid area may represent lines of various thicknesses, colored geometric shapes appearing in diagrams, or facets of 3D objects. Generating a display of a solid area requires determining 3 properties of the area, its mask, its shading rule, and its priority.

The mask of an area is a representation that defines which pixels lie within the solid area. A mask values represented in the form of matrix, 0 indicates a pixel outside the area and 1 indicates a pixel within the area. A shading rule specifies how to compute the intensity of each pixel within the area. If an image should contain more than one solid area, the priority of each area determines which area is displayed when two or more areas overlap.

Geometric Representation of Areas

A solid area representation, it must be possible to determine the three essential attributes of area, its mask, priority, and shading. A simple representation is a matrix of binary values. This requires no scan conversion and is often used to represent alphanumeric character shapes. Large areas require a more compact representation.

Some geometric figures have very simple representations and need only simple scan – conversion algorithms.

Scan – conversion algorithms

The scan conversion of a polygon involves finding all pixels that lie inside the polygon boundaries and generating a display by appropriately setting the intensities of these pixels inside or outside the polygon by counting intersection of boundary with an imaginary line extending from the point to some other point far outside the polygon. If an odd number of intersections are encountered, the point lies inside the boundary: otherwise it lies outside.

Coherence

If a given pixel is inside the polygon, immediately adjacent pixels are likely to be inside as well. A similar coherence holds for pixels outside the boundary.

The coherence property suggests that a number of adjacent pixels should be tested together. A convenient group to test is an entire scan line.

YX algorithm

Ref - book page no 232

Singularities

The yx scan conversion algorithms depend on calculating the coordinates of intersection between edges and scan lines. This calculation becomes difficult when a vertex of the polygon lies exactly on a scan line center. In this case it is crucial for proper number of intersections of the polygon boundary and scan line to be recorded, for it is only by counting intersections that scan conversion algorithm determines whether point lies inside or outside the polygon.

A reliable way to process singularities relies less on the numerical precision of calculations and more on the topology of the polygon. It makes use of the direction of successive edges of the polygon. If a polygon boundary progresses monotonically upward or downward , only single intersection with each scan line should be recorded.

When the direction changes from downward to upward, the intersection must be repeated.

Ref algorithm page 236.

Sampling

Polygon scan conversion algorithm fail to calculate the area of the polygon that falls under each pixel but are concerned only with mathematical points that lie at the center of each pixel.

For overcome this problem, we are using fraction algorithm. Since a precise calculations of the overlapping area can be quite costly, approximate methods are desirable. If we are using a display with very few intensity levels, there is no point in determining a precise value for the fractional area, because we shall be unable to make use of it.

Method 1 : single edge passes through the pixel at a steep angle, the precise location of the x intersection determined the fractional area covered.

Method 2:

Edges passes through a shadow angle

Method 3 : estimate area within the pixel, then scan convert.

Method4 : a precise method for calculating overlapping area is to use the polygon –clipping algorithm.

Ref fraction algorithm- page no 239.

Priority
Painter’s algorithm is an effective way to resolve priorities on a raster display. Each polygon assigned to a priority number and polygons are sorted by priority. The screen is cleared and polygons are scan converted and displayed in turn, starting with polygon low priority.

YX algorithm

The performance of a scan conversion algorithm is determined largely by the sorting steps it uses.

The yx algorithm generates the image from top to bottom, one scan line at a time

As it does so, it maintains an active edge list ,sorted by x, lisiting all edges that cross the scan line being prepared.

This algorithm reduces the sorting time.

Properties Of Scan Conversion Algorithm

Scan conversion of single polygon:

(YX)- simplest practical scan conversion algorithm

Y-X- Efficient sorting, taking advantage of edge cohernce

Scan conversion and priority resolution

P-(YX)- painters algorithm, the simplest way to resolve priority conflicts

(YPX)- update appears to flow down the screen but sorting inefficient

P-Y-X- Painters algorithm using faster Y-X sorting

Y-(PX)- Efficient sorting , with the update progressing down the screen.

Raster Graphics System

Graphical items can be represented as dots and lines defined by their Cartesian coordinates.

There are three different representation for basic items of graphical information

  1. Raster or rectangular arrays of intensity samples.
  2. Lines and dots I,e the same representation as in line –drawing systems
  3. Solid areas, defined by geometry of their outlines.

Raster Manipulation functions

  1. Write Rectangle
  2. Write mask
  3. Write color
  4. Copy raster
  5. Invert Mask
  6. Invert Rectangle

Ref the operations of this function in book page no 262.

System Using Raster Representation

A graphic package based on raster representations will need two kinds of facilities – representation and operations

Raster Representation

The system should provide a raster frame buffer whose contents are displayed on the screen. Defining representations for raster will require conventions for representing colors, for designating the transparent color and so forth.

It is not essential to provide many separate raster in order to allow combination operations to be performed. Instead we can provide one large raster , only part of which is displayed.

Raster Operations

Primitive operations are included in the system to modify and combine raster. Functions are SetPixel and GetPixel.

System Using Geomertric Representations

The main disadvantage of using geometric descriptions is the need to perform scan conversion .

Line Based Raster System

This limited form of raster graphics system uses only a simple kind of scan conversion, the DDA algorithm, and can therefore achieve relatively good performance.