A raster-scan display, compared to a random-scan (vector) display:

Handles filled areas naturally since every pixel in the frame buffer can be individually coloured

Steers the electron beam directly along the lines to be drawn

Cannot display filled regions at all

Redraws only the actual line segments each refresh

Bresenham's line-drawing algorithm is preferred over DDA chiefly because it:

Uses only integer arithmetic and is exact, with no accumulated rounding drift

Requires floating-point hardware

The midpoint circle algorithm exploits symmetry to compute pixels for only:

One octant (45°), reflecting the rest into the other seven

The whole circle, with no symmetry exploited

The midpoint ellipse algorithm needs two separate regions (unlike the circle algorithm's single octant), chiefly because:

An ellipse has only four-way (quadrant) symmetry since its two radii differ, and its slope crosses −1 within one quadrant

Ellipses cannot be drawn on raster displays

It uses floating-point arithmetic exclusively

An ellipse has no symmetry at all

Scan-line polygon filling fills pixels between:

Each pair of consecutive edge-intersections on a scan line, sorted by x

The topmost and bottommost pixels of the whole polygon

Every pixel on the screen regardless of the polygon

Flood-fill, compared to boundary-fill, decides where to stop spreading by:

Replacing every pixel matching the region's old interior colour, regardless of any separately-defined boundary

Stopping only at pixels matching a specific pre-defined boundary colour

Never stopping until the whole screen is filled

Requiring the region to have exactly four sides

Which of the following are true of random-scan (vector) displays? (More than one option may be correct.)

The electron beam is steered directly along the outlines to be drawn

They can flicker if the display list is too long to redraw within the persistence time

The electron beam is steered directly along the outlines to be drawn

They can flicker if the display list is too long to redraw within the persistence time

They store the image as a full pixel grid refreshed at a fixed rate

They are well suited for filled, realistic images

Computer Graphics Fundamentals

Computer Graphics is an entire named sub-item of Unit 3 with no GATE CS equivalent whatsoever. This chapter opens it with the physical/display fundamentals (raster versus random scan, display devices, input devices) and the classic rasterisation algorithms every graphics course opens with: drawing a line, a circle and an ellipse correctly and efficiently, and filling a closed region.

Raster-Scan and Random-Scan Systems, Display and Input Devices

Raster-scan versus random-scan (vector) displays
Property	Raster-scan	Random-scan (vector)
Image representation	A frame buffer of pixels, refreshed row by row at a fixed rate regardless of image content	The electron beam is steered directly along the lines to be drawn, redrawing only the actual line segments
Filled areas / realistic images	Handled naturally — every pixel can be individually coloured	Poorly suited — designed for outlines, not filled regions
Common artefact	Jagged/aliased diagonal lines from the fixed pixel grid	Flicker if the display list is too long to redraw within the persistence time

Input devices are classified by what they report: LOCATOR devices (mouse, joystick, trackball) report a position; VALUATOR devices report a scalar value along a dial; a KEYBOARD reports discrete symbolic tokens; a SCANNER/DIGITISER converts an existing physical image into pixel data. Points and lines are the two primitive geometric objects every raster display ultimately builds everything else from — a point is one addressed pixel, and a line must be approximated by choosing which pixels along its path to light, which is exactly the problem the line-drawing algorithms below solve.

Line-Drawing Algorithms

DDA (Digital Differential Analyzer): for slope m = Δy/Δx with |m| ≤ 1, step x by 1 each iteration and accumulate y += m, rounding to the nearest pixel — simple, but its floating-point accumulation is slower and accumulates rounding error over a long line.
Bresenham's algorithm: reformulates the same decision using only INTEGER arithmetic by tracking a decision variable that measures which of two candidate next pixels is closer to the true line — this avoids floating point entirely, is exact (no accumulated rounding drift) and is the standard production algorithm for exactly that reason.

🎯 Why Bresenham beats DDA for production use

DDA's per-step floating-point addition and rounding is both slower on integer-only hardware and subject to cumulative rounding error over a long line — the pixel chosen at step 10,000 can drift from where the true line actually is. Bresenham's integer decision variable is updated by simple integer addition/subtraction each step and is provably exact, choosing the pixel closest to the true line at every single step with no drift at all — this exactness, not merely the speed, is the reason it is the standard taught first.

Midpoint Circle and Ellipse Algorithms

Midpoint circle algorithm: exploits EIGHT-WAY (octant) symmetry — computing pixels for just one 45° octant and reflecting them into the other seven — and at each step tests a decision parameter based on the midpoint between two candidate pixels to choose which one is closer to the true circle, again with pure integer updates.
Midpoint ellipse algorithm: the same idea, but with only FOUR-WAY (quadrant) symmetry, since an ellipse's two radii differ, and it is split into TWO REGIONS (where the curve's slope is above versus below −1, i.e. where it is 'more horizontal' versus 'more vertical'), with a separate stepping rule and decision parameter for each region.

Scan-Line Polygon Fill, Boundary-Fill and Flood-Fill

Scan-line polygon fill: for each horizontal scan line, find its intersections with the polygon's edges, sort them by x, and fill the pixels between each PAIR of intersections (using the even-odd or nonzero winding rule to decide interior versus exterior when the polygon is concave or self-intersecting).
Boundary-fill and flood-fill: both start from a seed pixel inside a region and spread to neighbours (4-connected or 8-connected). Boundary-fill stops spreading at pixels matching a specific BOUNDARY colour; flood-fill instead replaces every pixel matching the region's OLD interior colour with a new one, regardless of any separately-defined boundary — the right choice depends on whether the region is bounded by one consistent colour or defined by its own current fill colour.

Key takeaways

A raster-scan display refreshes a full frame buffer at a fixed rate and handles filled areas naturally; a random-scan (vector) display steers a beam along outlines and is prone to flicker with a long display list.
Bresenham's line algorithm uses pure integer arithmetic and is exact, unlike DDA's floating-point accumulation which drifts over a long line.
The midpoint circle algorithm uses eight-way symmetry; the midpoint ellipse algorithm uses only four-way symmetry and splits into two slope regions, since the two radii differ.
Scan-line polygon fill fills between pairs of edge-intersections per row; the winding rule decides interior/exterior for concave or self-intersecting polygons.
Boundary-fill stops at a defined boundary colour; flood-fill replaces every pixel of the old interior colour — the right choice depends on how the region is defined.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A raster-scan display, compared to a random-scan (vector) display:
1. Handles filled areas naturally since every pixel in the frame buffer can be individually coloured
2. Steers the electron beam directly along the lines to be drawn
3. Cannot display filled regions at all
4. Redraws only the actual line segments each refresh
Show answer
Answer: A — Handles filled areas naturally since every pixel in the frame buffer can be individually coloured
A raster display refreshes its whole pixel grid regardless of content, so filled regions are just as natural as outlines; the other three options describe a random-scan (vector) display instead.
Bresenham's line-drawing algorithm is preferred over DDA chiefly because it:
1. Uses only integer arithmetic and is exact, with no accumulated rounding drift
2. Draws circles instead of lines
3. Requires floating-point hardware
4. Only works for vertical lines
Show answer
Answer: A — Uses only integer arithmetic and is exact, with no accumulated rounding drift
Bresenham reformulates the pixel-choice decision as integer addition/subtraction on a decision variable, avoiding both the speed cost and the cumulative rounding error of DDA's floating-point accumulation.
The midpoint circle algorithm exploits symmetry to compute pixels for only:
1. One octant (45°), reflecting the rest into the other seven
2. One quadrant only
3. The whole circle, with no symmetry exploited
4. Half the circle only
Show answer
Answer: A — One octant (45°), reflecting the rest into the other seven
A circle's eight-way symmetry means computing one 45° octant's pixels and reflecting them (swapping and negating x/y coordinates appropriately) gives all eight octants for free.
The midpoint ellipse algorithm needs two separate regions (unlike the circle algorithm's single octant), chiefly because:
1. An ellipse has only four-way (quadrant) symmetry since its two radii differ, and its slope crosses −1 within one quadrant
2. Ellipses cannot be drawn on raster displays
3. It uses floating-point arithmetic exclusively
4. An ellipse has no symmetry at all
Show answer
Answer: A — An ellipse has only four-way (quadrant) symmetry since its two radii differ, and its slope crosses −1 within one quadrant
With unequal radii, an ellipse's octant-level symmetry breaks down to only quadrant-level, and within one quadrant the curve's slope still crosses −1, requiring a different stepping direction (and decision parameter) on either side of that crossing.
Scan-line polygon filling fills pixels between:
1. Each pair of consecutive edge-intersections on a scan line, sorted by x
2. The topmost and bottommost pixels of the whole polygon
3. Every pixel on the screen regardless of the polygon
4. Only the polygon's vertices
Show answer
Answer: A — Each pair of consecutive edge-intersections on a scan line, sorted by x
For each scan line, the edge-intersections are sorted by x-coordinate and interior spans alternate with exterior spans between consecutive intersections — filling between each pair is what produces the correct interior, including for concave shapes.
Flood-fill, compared to boundary-fill, decides where to stop spreading by:
1. Replacing every pixel matching the region's old interior colour, regardless of any separately-defined boundary
2. Stopping only at pixels matching a specific pre-defined boundary colour
3. Never stopping until the whole screen is filled
4. Requiring the region to have exactly four sides
Show answer
Answer: A — Replacing every pixel matching the region's old interior colour, regardless of any separately-defined boundary
Boundary-fill is defined against a fixed boundary colour; flood-fill instead uses the region's own current (old) interior colour as the criterion, replacing every matching pixel with the new colour — which is why it works even on regions with no single consistently-coloured boundary.
Which of the following are true of random-scan (vector) displays? (More than one option may be correct.)
1. The electron beam is steered directly along the outlines to be drawn
2. They can flicker if the display list is too long to redraw within the persistence time
3. They store the image as a full pixel grid refreshed at a fixed rate
4. They are well suited for filled, realistic images
Show answer
Answer: A — The electron beam is steered directly along the outlines to be drawn; B — They can flicker if the display list is too long to redraw within the persistence time
The first two describe random-scan displays correctly; the last two describe raster-scan displays instead — a frame buffer and natural handling of filled areas are raster properties, not vector ones.
Name the line-drawing algorithm that reformulates the pixel-choice decision using only integer arithmetic, avoiding the accumulated rounding drift of the DDA method.
Numerical answer — type the value.
Show answer
Answer: Bresenham
Bresenham's algorithm is the standard integer-only, exact line-drawing method, and its decision-variable technique generalises to the midpoint circle and ellipse algorithms as well.