BSc CSIT (TU) Science Computer Graphics (BSc CSIT, CSC209) Question Paper 2079 Nepal

Bresenham's Line Drawing Algorithm

Bresenham's algorithm is an efficient, integer-only incremental method to scan-convert a line. It uses a decision parameter to choose, at each step, between the two candidate pixels nearest to the true line, avoiding floating-point arithmetic and rounding.

Derivation (for slope $0 < m < 1$)

For a line $y = mx + c$ with $m = \dfrac{\Delta y}{\Delta x}$, after plotting pixel $(x_k, y_k)$ the next $x$ is $x_k+1$ and we must choose between $y_k$ (lower) and $y_k+1$ (upper). The decision parameter is:

plot(x0, y0)
for each x from x0+1 to x1:
    if p < 0:  p += 2*dy
    else:      y++;  p += 2*dy - 2*dx
    plot(x, y)

Digitizing (20, 10) to (30, 18)

$\Delta x = 30-20 = 10,\quad \Delta y = 18-10 = 8,\quad m = 0.8$ (so $0<m<1$).

$2\Delta y = 16,\quad 2\Delta y - 2\Delta x = 16-20 = -4$

Initial $p_0 = 2\Delta y - \Delta x = 16-10 = 6$. Start pixel $(20,10)$.

Plotted pixels: (20,10), (21,11), (22,12), (23,12), (24,13), (25,14), (26,15), (27,16), (28,16), (29,17), (30,18).

Midpoint Circle Drawing Algorithm

Derivation

For a circle of radius $r$ centred at the origin, the implicit function is:

where $f<0$ inside, $f=0$ on, and $f>0$ outside the circle. We use 8-way symmetry, computing only the second octant ($x$ from 0 to $x=y$, where slope $\le 1$) and reflecting.

After plotting $(x_k, y_k)$, the next $x$ is $x_k+1$. We test the midpoint between the two candidate pixels $y_k$ and $y_k-1$, i.e. at $(x_k+1,\; y_k-\tfrac12)$:

• If $p_k < 0$: midpoint inside $\Rightarrow$ choose $y_{k+1}=y_k$, and $p_{k+1}=p_k + 2x_{k+1}+1$.
• If $p_k \ge 0$: midpoint outside $\Rightarrow$ choose $y_{k+1}=y_k-1$, and $p_{k+1}=p_k + 2x_{k+1}+1 - 2y_{k+1}$.

Starting at $(0, r)$, the initial decision parameter is:

Plotting for $r=10$, centre origin (first octant)

$p_0 = 1 - 10 = -9$. Start $(0,10)$. Iterate until $x \ge y$.

First-octant pixels: (0,10), (1,10), (2,10), (3,10), (4,9), (5,9), (6,8), (7,7).

The full circle is obtained by reflecting these across all eight octants: $(\pm x,\pm y)$ and $(\pm y,\pm x)$.

2D Geometric Transformation

A 2D geometric transformation is an operation that changes the position, orientation, or size of an object in the 2D plane by mapping each point $(x,y)$ to a new point $(x',y')$. Using homogeneous coordinates a point is written as $(x, y, 1)$, so that all three basic transformations can be expressed as $3\times3$ matrix multiplication and composed by multiplying matrices.

1. Translation

Shifts every point by $(t_x, t_y)$:

Homogeneous coordinates are needed because translation is not linear in $(x,y)$ alone (cannot be a $2\times2$ matrix).

2. Rotation (about origin, angle $\theta$, counter-clockwise)

3. Scaling (about origin, factors $s_x, s_y$)

If $s_x = s_y$ the scaling is uniform; otherwise it is differential. A point is transformed as $P' = M \cdot P$ where $P = [x\; y\; 1]^T$, and composite transforms are formed by matrix multiplication (applied right to left).

Raster Scan vs Random (Vector) Scan Display

Raster Scan Display

The screen is a grid of pixels. The electron beam sweeps the entire screen one horizontal line (scan line) at a time, from top-left to bottom-right, in a fixed raster pattern. Picture intensity for every pixel is stored in a frame buffer (refresh buffer) in memory; the beam reads this buffer and turns the beam on/off (or sets intensity) as it scans. The whole screen is refreshed typically 60–80 times per second. Suited for realistic, shaded, filled images (used in TVs and modern monitors), but suffers from aliasing (staircase) effects and needs large memory.

Random (Vector / Stroke) Scan Display

The electron beam is deflected directly from one endpoint of a line to another, drawing only the line segments that make up the picture (not the whole screen). The picture is stored as a set of line-drawing commands in a display list / display file, which the display processor repeatedly executes to refresh the image. It produces smooth, high-resolution lines (no jagged edges) and is ideal for line drawings (CAD, engineering). However, it cannot easily display shaded/filled areas, and refresh time grows with picture complexity.

DDA (Digital Differential Analyzer) Line Algorithm

DDA is an incremental scan-conversion algorithm that computes intermediate pixel positions by sampling the line at unit intervals along the axis of greater change and rounding the result.

Algorithm

For a line from $(x_1,y_1)$ to $(x_2,y_2)$ with $\Delta x = x_2-x_1$, $\Delta y = y_2-y_1$:

steps = max(|dx|, |dy|)
x_inc = dx / steps
y_inc = dy / steps
x = x1;  y = y1
for i = 0 to steps:
    plot(round(x), round(y))
    x = x + x_inc
    y = y + y_inc

If $|m| \le 1$, increment $x$ by 1 and $y$ by $m$ each step; if $|m| > 1$, increment $y$ by 1 and $x$ by $1/m$.

Advantages

• Simpler and faster than directly evaluating $y = mx + c$ for every $x$ (no multiplication inside the loop).
• Easy to understand and implement; works for lines of any slope.

Disadvantages

• Uses floating-point arithmetic and round(), which is slower and less accurate than integer methods like Bresenham's.
• Accumulation of round-off error can cause the plotted pixels to drift away from the true line for long lines.

Rotation About an Arbitrary Point in 2D

The standard rotation matrix rotates about the origin only. To rotate an object by angle $\theta$ about an arbitrary pivot point $(x_p, y_p)$, we compose three transformations:

1. Translate the pivot to the origin: $T(-x_p, -y_p)$.
2. Rotate about the origin by $\theta$: $R(\theta)$.
3. Translate back: $T(x_p, y_p)$.

The composite matrix (applied right to left to a point) is:

Multiplying gives:

Thus the new coordinates are:

Sutherland-Hodgman Polygon Clipping Algorithm

This algorithm clips a polygon against a convex clipping window by clipping the polygon successively against each window edge (left, right, bottom, top). The output polygon from clipping against one edge becomes the input for the next edge.

Procedure

For each clipping edge, the polygon's vertices are processed as ordered edges $(S \to P)$. For each edge there are four cases (based on whether $S$ and $P$ are inside the boundary):

Here $I$ is the intersection of edge $SP$ with the clipping boundary. After processing all four window edges, the remaining vertices form the clipped polygon.

Example

Clip triangle with vertices $A(1,1), B(5,1), C(3,5)$ against the right window edge $x = 4$:

• Edge $A\to B$: both inside ($x<4$) $\Rightarrow$ output $B$. (A handled by previous edge.)
• Edge $B\to C$: $B$ inside, $C$ inside? $C$ has $x=3<4$, inside; but $B(5,1)$ is outside. So $B$ out, $C$ in $\Rightarrow$ output intersection of $BC$ with $x=4$, then $C$.

The result is a clipped polygon lying entirely within $x \le 4$. Limitation: it works correctly only for convex clipping windows and may leave spurious connecting edges when clipping concave polygons.

RGB and CMY Color Models

RGB (Red, Green, Blue) Model

RGB is an additive color model based on adding light. The three primaries — Red, Green, Blue — are combined in varying intensities; adding all three at full intensity produces white, and zero of all three gives black. It is represented as a unit cube with the origin $(0,0,0)$ = black and $(1,1,1)$ = white. RGB is used by emissive devices that generate light: CRT/LCD monitors, TVs, scanners, and cameras.

CMY (Cyan, Magenta, Yellow) Model

CMY is a subtractive color model based on absorbing (subtracting) light from white. Its primaries — Cyan, Magenta, Yellow — are the complements of RGB. Adding all three ideally gives black, and zero gives white (the paper). It is used by reflective devices such as printers and plotters where pigments absorb wavelengths.

Conversion

CMY is the complement of RGB (for unit-normalized values):

(In practice CMYK adds a black, $K$, channel for true blacks and ink economy.)

3D Transformation Matrices (Homogeneous Coordinates)

In 3D, points are represented as $(x, y, z, 1)$ and transformations as $4\times4$ matrices.

1. Translation by $(t_x, t_y, t_z)$

2. Scaling by factors $(s_x, s_y, s_z)$ about origin

3. Rotation about the X-axis by angle $\theta$

The $x$ coordinate is unchanged; $y$ and $z$ rotate:

so that $x'=x,\; y'=y\cos\theta - z\sin\theta,\; z'=y\sin\theta + z\cos\theta$.

Window-to-Viewport Transformation

A window is a rectangular region selected in the world-coordinate system that defines what part of the scene is shown. A viewport is a rectangular region on the display device (in device/screen coordinates) that defines where it is shown. The window-to-viewport transformation (viewing transformation) maps points from window coordinates to viewport coordinates while preserving relative positions.

Mapping

Let the window be bounded by $(xw_{min}, yw_{min})$–$(xw_{max}, yw_{max})$ and the viewport by $(xv_{min}, yv_{min})$–$(xv_{max}, yv_{max})$. A window point $(x_w, y_w)$ maps to viewport point $(x_v, y_v)$ keeping the same relative proportion:

$S_x$ and $S_y$ are the scaling factors. If $S_x = S_y$ the aspect ratio is preserved; otherwise the image is stretched. The transformation is effectively translate window to origin → scale by $(S_x,S_y)$ → translate to viewport.

Parallel vs Perspective Projection

Projection transforms 3D objects onto a 2D view (projection) plane using projectors (lines from object points to the plane).

Parallel Projection

The projectors are parallel to one another (the centre of projection is at infinity). Object dimensions and parallelism are preserved, so it does not give a realistic sense of depth but is accurate for measurements. Used in engineering/CAD drawings (orthographic, oblique).

Perspective Projection

The projectors converge at a single point called the centre of projection (eye). Objects farther from the viewer appear smaller (foreshortening), giving a realistic appearance with vanishing points. Parallel lines (not parallel to the plane) appear to meet. Used in realistic rendering, games, and architecture views.

Working of a CRT (Cathode Ray Tube)

A CRT is a vacuum tube that produces images by directing a focused beam of electrons onto a phosphor-coated screen.

Main Components and Operation

1. Electron Gun (cathode + control grid): A heated cathode (filament) emits electrons by thermionic emission. The control grid regulates the number of electrons (beam intensity / brightness).
2. Focusing System: Electrostatic (or magnetic) lenses converge the electrons into a fine, sharp beam so it strikes the screen as a small spot.
3. Accelerating Anode: A high positive voltage accelerates the electrons toward the screen, giving them enough energy to excite the phosphor.
4. Deflection System: Horizontal and vertical deflection plates (or coils) bend the beam to position the spot anywhere on the screen.
5. Phosphor-Coated Screen: When the high-speed electrons strike the phosphor, it emits light at that point. The brief glow is called persistence; the image is kept visible by refreshing (redrawing) it many times per second (e.g. 60 Hz).

Diagram (described)

From left to right: heated cathode/filament → control grid → focusing anode → accelerating anode → (beam passes between) vertical and horizontal deflection plates → narrow beam → phosphor screen at the right where the glowing spot appears. The connecting electron beam runs along the central axis of the evacuated glass tube.

Color CRTs use three electron guns (R, G, B) and a shadow mask so each beam strikes only its corresponding phosphor dots.