Computer Graphics & Multimedia (AD-503 (B)) Unit 1 Notes

How unit 1 is examined

This unit covers raster and random scan display systems, and the scan-conversion algorithms for lines, circles and polygon fill; no topic was asked in the supplied papers, so each is kept short but complete.

Introduction to Raster Scan displays

Not asked since 2022

Definition. A raster scan display draws the picture as a grid of pixels by sweeping the electron beam across the screen line by line, from top to bottom, while the picture is held in a refresh buffer.

Key points.

The beam moves left to right along each scan line, switches off during horizontal retrace, and returns to the top during vertical retrace.
The beam intensity is turned on or off for every pixel, so the same system shows lines, filled areas and shaded images.
The refresh rate is the number of times per second the whole screen is redrawn, typically 60 Hz or more, to avoid flicker.
Interlacing draws the odd lines first and the even lines next, which halves the flicker at the same bandwidth.

Pixels

Definition. A pixel (picture element) is the smallest addressable point of the screen whose intensity and colour can be controlled.

Key points.

Resolution is the number of pixels along the width and height, for example $1920 \times 1080$.
Total pixels $= \text{columns} \times \text{rows}$, so a higher resolution gives a sharper picture but needs more memory.
Pixel positions are given by integer coordinates $(x, y)$ with the origin at the top-left corner.
Aspect ratio is the ratio of width to height, such as 4:3 or 16:9.

Frame buffer

Definition. The frame buffer (refresh buffer) is the memory area that stores the intensity value of every pixel of the screen, and the display controller reads it repeatedly to refresh the screen.

Key points.

Each pixel needs a number of bits called bit planes or depth; a 1-bit plane gives a monochrome image and 8 bits give 256 colours or grey levels.
Frame buffer size in bits $= \text{width} \times \text{height} \times \text{bits per pixel}$.
For example, a $1024 \times 768$ screen with 8 bits per pixel needs $1024 \times 768 \times 8 = 6{,}291{,}456$ bits, which is 768 KB.
A colour look-up table can map a small pixel value to a wider colour, saving memory.

Vector & Character generation

Definition. A vector display draws a picture as a set of straight line segments given by endpoints, and character generation produces letters either from stroke lines or from dot-matrix patterns.

Key points.

In the stroke method each character is drawn as a sequence of short line segments, which is easy to scale and rotate.
In the dot-matrix method each character is a small grid such as $5 \times 7$ whose bits say which pixels are on.
In the starburst method a character is built from a fixed pattern of 24 line segments, of which the required ones are switched on.
Vector generators draw lines directly, whereas a raster system must approximate them by scan conversion.

Random Scan systems

Definition. A random scan (vector) system directs the electron beam only to the parts of the screen where the picture has to be drawn, one line at a time, in any order.

Key points.

The picture is stored as a display list of line-drawing commands in the refresh display file, and it is redrawn 30 to 60 times per second.
It gives very smooth lines with high resolution, but it cannot fill areas or show realistic shaded scenes.
Refresh time depends on the number of lines, so a complex picture flickers.
It suits line drawings such as CAD, while raster scan suits general images.

Display devices

Definition. A display device is the output hardware that turns the frame buffer contents into a visible picture; common types are CRT, LCD and LED displays.

Key points.

A CRT has an electron gun, focusing and deflection systems and a phosphor-coated screen that glows where the beam strikes it.
An LCD holds liquid crystal between polarising sheets and a backlight, and the applied voltage controls how much light passes.
An LED display uses light-emitting diodes as the backlight or as the pixels themselves, giving thinner, brighter and more efficient screens.
LCD and LED screens are flat and consume less power than a CRT, but a CRT gave wider viewing angles and colour range in older systems.

Scan Conversion techniques

Definition. Scan conversion is the process of converting a geometric primitive such as a line, circle or polygon into the set of pixels that best represents it on the raster grid.

Key points.

Because pixel positions are integers, an ideal shape is approximated by choosing the nearest pixels, which causes the jagged effect called aliasing.
A good algorithm is fast, uses integer arithmetic where possible, and produces a continuous, uniformly bright shape.
Lines are converted by DDA and Bresenham, circles by the midpoint method, and areas by fill algorithms.
Each pixel found is written into the frame buffer at $(x, y)$.

Line Drawing algorithms: simple DDA, Bresenham’s Algorithm

Definition. DDA and Bresenham’s algorithm are incremental methods that find the pixels lying closest to the line from $(x_1, y_1)$ to $(x_2, y_2)$.

Key points.

In DDA, $dx = x_2 - x_1$, $dy = y_2 - y_1$, and $\text{steps} = \max(|dx|, |dy|)$; then $x_{inc} = dx/\text{steps}$, $y_{inc} = dy/\text{steps}$, and each step adds the increments and plots the rounded point.
DDA is simple but uses floating-point addition and rounding, so error accumulates on long lines.
Bresenham (slope $0 < m < 1$) uses $p_0 = 2\,dy - dx$; if $p_k < 0$ plot $(x+1, y)$ and $p_{k+1} = p_k + 2\,dy$, else plot $(x+1, y+1)$ and $p_{k+1} = p_k + 2\,dy - 2\,dx$.
Bresenham uses only integer addition, so it is faster and more accurate than DDA.

Circle Drawing Algorithms: Midpoint Circle drawing and Bresenham’s Algorithm

Definition. The midpoint circle algorithm plots one octant of a circle of radius $r$ from $(0, r)$ using an integer decision parameter and obtains the other seven octants by symmetry.

Key points.

The initial decision parameter is $p_0 = 1 - r$, and $x$ increases by 1 at every step.
If $p_k < 0$, the next point is $(x+1, y)$ and $p_{k+1} = p_k + 2x_{k+1} + 1$.
Otherwise the next point is $(x+1, y-1)$ and $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$; the loop stops when $x \ge y$.
Each computed $(x, y)$ is plotted eight times as $(\pm x, \pm y)$ and $(\pm y, \pm x)$, shifted by the centre. Bresenham’s circle is the same idea with $d_0 = 3 - 2r$.

Polygon fill algorithm: Boundary-fill and Flood-fill algorithms

Definition. Boundary-fill and flood-fill are seed-based methods that colour the interior of a region, starting from an interior point and spreading to neighbouring pixels.

Key points.

Boundary-fill spreads from the seed until it meets pixels of the given boundary colour, so it needs a region with a single-colour boundary.
Flood-fill replaces every connected pixel of the old interior colour with the new colour, so it works for regions without a uniform boundary.
Both use 4-connected neighbours (left, right, up, down) or 8-connected neighbours (adding the diagonals); 4-connected fill leaks less through diagonal gaps.
They are implemented recursively or with a stack, and a recursive version may overflow the stack on large regions.

Last-minute revision

Raster scan draws line by line from a frame buffer; refresh rate is typically 60 Hz or more.
Frame buffer size $= \text{width} \times \text{height} \times \text{bits per pixel}$.
$1024 \times 768$ at 8 bits per pixel is 768 KB.
Random scan draws only the lines of the picture from a display list; it is smooth but cannot fill areas.
DDA: $\text{steps} = \max(|dx|, |dy|)$, increments $dx/\text{steps}$ and $dy/\text{steps}$.
Bresenham line: $p_0 = 2\,dy - dx$; add $2\,dy$ if $p<0$, else add $2\,dy - 2\,dx$.
Midpoint circle: $p_0 = 1 - r$; stops when $x \ge y$; eight-way symmetry.
Bresenham circle: $d_0 = 3 - 2r$.
Boundary-fill stops at a boundary colour; flood-fill replaces an old interior colour.
4-connected uses 4 neighbours, 8-connected uses 8.

Memory hooks

Raster = "row by row", random = "route only where the lines are".
DDA = "Divide by steps, Add, round"; Bresenham = "Bits only, integers".
Midpoint circle: start at $1 - r$, go one octant, mirror eight times.
Boundary-fill hits a wall; flood-fill replaces a colour.

Coverage checklist

Introduction to Raster Scan displays: covered, no past questions.
Pixels: covered, no past questions.
Frame buffer: covered, no past questions.
Vector & Character generation: covered, no past questions.
Random Scan systems: covered, no past questions.
Display devices: covered, no past questions.
Scan Conversion techniques: covered, no past questions.
Line Drawing algorithms: simple DDA, Bresenham’s Algorithm: covered, no past questions.
Circle Drawing Algorithms: Midpoint Circle drawing and Bresenham’s Algorithm: covered, no past questions.
Polygon fill algorithm: Boundary-fill and Flood-fill algorithms: covered, no past questions.

Account

Computer Graphics & Multimedia (AD-503 (B)) - Unit 1 Short Notes

How unit 1 is examined

Introduction to Raster Scan displays

Pixels

Frame buffer

Vector & Character generation

Random Scan systems

Display devices

Scan Conversion techniques

Line Drawing algorithms: simple DDA, Bresenham’s Algorithm

Circle Drawing Algorithms: Midpoint Circle drawing and Bresenham’s Algorithm

Polygon fill algorithm: Boundary-fill and Flood-fill algorithms

Last-minute revision

Memory hooks

Coverage checklist