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

Bresenham's Line Drawing Algorithm

Bresenham's algorithm is an efficient, incremental integer algorithm for scan-converting a line. It uses only integer addition, subtraction and bit-shifting (no floating point or division), choosing at each step the pixel closest to the true line by means of a decision parameter $p_k$.

Derivation (for $0 \le m \le 1$, line drawn left to right)

At step $k$ the pixel $(x_k, y_k)$ has been plotted. The next $x$ is $x_k+1$ and the choice is between $y_k$ (lower) and $y_k+1$ (upper). With $\Delta x = x_2-x_1$, $\Delta y = y_2-y_1$ the decision parameter is:

Algorithm

1. Input endpoints (x1,y1),(x2,y2)
2. dx = x2-x1, dy = y2-y1
3. Plot (x1,y1)
4. p = 2*dy - dx
5. for x = x1 to x2-1:
     if p < 0:  y stays;          p = p + 2*dy
     else:       y = y + 1;        p = p + 2*dy - 2*dx
     x = x + 1
     plot(x, y)

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

$\Delta x = 30-20 = 10$, $\Delta y = 18-10 = 8$. Since $0 \le m = 8/10 \le 1$, step in $x$.

$2\Delta y = 16$, $\ 2\Delta y - 2\Delta x = 16-20 = -4$. Initial $p_0 = 2\Delta y - \Delta x = 16-10 = 6$.

Pixels plotted: (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

The circle $x^2+y^2=r^2$ is symmetric in 8 octants, so we compute only the first octant (from $x=0,\ y=r$ to $x=y$) and reflect. Define the circle function:

which is $<0$ inside, $=0$ on, and $>0$ outside the circle.

Having plotted $(x_k,y_k)$, the next $x$ is $x_k+1$; the choice is between $y_k$ and $y_k-1$. We evaluate $f$ at the midpoint $\left(x_k+1,\ y_k-\tfrac12\right)$, giving the decision parameter:

• If $p_k < 0$, midpoint is inside ⇒ choose $y_{k+1}=y_k$, and

• If $p_k \ge 0$, midpoint is outside ⇒ choose $y_{k+1}=y_k-1$, and

Initial value at $(0,r)$:

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

$p_0 = 1-10 = -9$. Start at $(0,10)$.

Stop when $x \ge y$ (here $x=7,y=7$).

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

The full circle is obtained by 8-way symmetry: $(\pm x,\pm y)$ and $(\pm y,\pm x)$.

2D Geometric Transformation

A 2D geometric transformation changes the position, orientation, size or shape of an object in the plane by modifying the coordinates of its defining points according to a rule. Using homogeneous coordinates a point $(x,y)$ is written as $(x,y,1)$, which lets translation, rotation and scaling all be expressed as $3\times3$ matrix multiplications and combined (composed) by multiplying matrices.

1. Translation

Shifts every point by $(t_x, t_y)$: $x'=x+t_x,\ y'=y+t_y$.

2. Rotation (about origin, angle $\theta$, anticlockwise)

$x'=x\cos\theta-y\sin\theta,\ \ y'=x\sin\theta+y\cos\theta$.

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

$x'=s_x\,x,\ \ y'=s_y\,y$.

If $s_x=s_y$ the scaling is uniform; otherwise it is differential and distorts shape.

Composition: A sequence of transformations is applied by multiplying their matrices, e.g. rotate-then-translate $= T\cdot R$, allowing complex transforms (like rotation about an arbitrary point) to be built from these basic ones.

Raster Scan vs Random (Vector) Scan Display

Raster Scan Display

The screen is a grid of pixels. The electron beam sweeps the screen row by row (left to right, top to bottom), one horizontal scan line at a time, refreshing the whole screen typically 60–80 times per second. The picture is stored as intensity values for every pixel in a memory area called the frame buffer (refresh buffer); the beam intensity is turned on/off according to these values. It can display filled areas, shaded regions and realistic images, and is the basis of modern displays (TV, monitors). Image quality depends on resolution, and lines may show a staircase (aliasing) effect.

Random / Vector Scan Display

The electron beam is deflected directly from one endpoint to another to draw line segments (strokes), tracing only the parts of the screen where the picture lies. The picture is stored as a set of line-drawing commands in a display file and redrawn (refreshed) ~30–60 times/sec. It produces smooth, high-resolution lines with no staircasing, but cannot easily display shaded/filled areas and is suited to line drawings (CAD, wireframes).

DDA (Digital Differential Analyzer) Line Algorithm

DDA is an incremental line-scan algorithm that samples the line at unit intervals along the axis of greater change and computes the other coordinate using the slope $m=\Delta y/\Delta x$.

Algorithm

1. dx = x2 - x1,  dy = y2 - y1
2. steps = max(|dx|, |dy|)
3. xinc = dx/steps,  yinc = dy/steps
4. x = x1,  y = y1
5. for i = 0 to steps:
     plot(round(x), round(y))
     x = x + xinc
     y = y + yinc

Each new point is found by adding a constant increment, then rounding to the nearest pixel.

Advantages

• Simpler and faster than the direct line equation ($y=mx+c$) since it avoids repeated multiplication; uses only repeated addition.
• Works for lines of any slope.

Disadvantages

• Uses floating-point arithmetic and rounding, which is slower and accumulates round-off error for long lines, causing the line to drift from its true path.
• Round operation is time-consuming compared to Bresenham's pure-integer method, making DDA less efficient.

Rotation About an Arbitrary Point in 2D

To rotate an object by angle $\theta$ about an arbitrary pivot $P(x_p, y_p)$ (not the origin), we perform three steps:

Step 1 — Translate the pivot to the origin: $T(-x_p,-y_p)$

Step 2 — Rotate about the origin by $\theta$:

Step 3 — Translate back to $P$: $T(x_p,y_p)$

The composite matrix is $M = T_2 \cdot R \cdot T_1$:

Thus the transformed point is $\begin{bmatrix}x'\\y'\\1\end{bmatrix}=M\begin{bmatrix}x\\y\\1\end{bmatrix}$, giving:

Sutherland–Hodgman Polygon Clipping

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

Rule for each edge

For every polygon edge from vertex $S$ to vertex $P$, four cases arise (with respect to the current clip boundary; inside = visible side):

Intersection $I$ of edge $SP$ with the boundary is computed by parametric/line equations.

Example

Clip triangle with vertices $A(1,1),\ B(5,1),\ C(3,4)$ against a rectangular window $x_{min}=2,\ x_{max}=4,\ y_{min}=0,\ y_{max}=3$.

• Left edge $x=2$: keep parts with $x\ge2$. Edge $A\!\to\!B$ ($A$ out, $B$ in) gives intersection $(2,1)$ then $B$; $B\!\to\!C$ both in/cross; $C\!\to\!A$ gives intersection. Output replaces the left-cut corner with new vertices on $x=2$.
• The intermediate polygon is then clipped against right ($x=4$), bottom ($y=0$) and top ($y=3$) edges in turn.

After all four passes the result is the polygon lying entirely inside the window. The algorithm is simple and well-suited to hardware, but for concave polygons it may produce extraneous connecting edges.

RGB and CMY Colour Models

RGB Model (additive)

Uses the three primary colours of light — Red, Green, Blue — represented along the axes of a unit cube. Colours are formed by adding light:

• $(0,0,0)$ = black (origin), $(1,1,1)$ = white.
• $R+G+B$: Red+Green = Yellow, Green+Blue = Cyan, Red+Blue = Magenta.
• Used by emissive devices: monitors, TVs, cameras, scanners.

CMY Model (subtractive)

Uses Cyan, Magenta, Yellow — the complements of RGB — which work by subtracting (absorbing) light reflected from a surface. Used for hard-copy/printing (inks/pigments on white paper):

• $(0,0,0)$ = white (paper), $(1,1,1)$ = black.
• Cyan absorbs red, Magenta absorbs green, Yellow absorbs blue.

Conversion

(In printing, CMYK adds a separate black, K, for richer blacks.)

3D Transformation Matrices (Homogeneous Coordinates)

A 3D point is $(x,y,z,1)$ and transforms use $4\times4$ matrices.

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

2. Scaling by $(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 $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 is to be displayed. A viewport is a rectangular region of the device/screen (normalized) coordinates that defines where it will be displayed. The window-to-viewport (or viewing) transformation maps each point inside the window to a corresponding point inside the viewport, preserving relative positions.

A window point $(x_w, y_w)$ maps to viewport point $(x_v, y_v)$ by keeping equal relative position:

Solving gives:

with scale factors

This is equivalent to: translate the window to the origin, scale by $(s_x,s_y)$, then translate to the viewport position. If $s_x \ne s_y$ the image is distorted in aspect ratio.

Parallel vs Perspective Projection

Projection maps 3D points onto a 2D view (projection) plane using projectors. The two main classes differ in where the projectors converge.

Summary: Parallel projection preserves relative proportions and is used where accurate measurement matters; perspective projection adds depth realism by making farther objects smaller, at the cost of true scale.

Cathode Ray Tube (CRT)

A CRT is the basic display device that produces images by directing a focused beam of electrons onto a phosphor-coated screen.

Diagram (described)

A sealed, evacuated glass tube. From the rear: heated cathode/filament → control grid → focusing and accelerating anodes (electron gun) → horizontal & vertical deflection plates (or coils) → phosphor-coated screen at the front.

Working

1. Electron generation: The heated cathode (filament) emits electrons by thermionic emission.
2. Intensity control: The control grid regulates the number of electrons (beam intensity/brightness).
3. Focusing & acceleration: The focusing anode narrows the electrons into a fine beam, and accelerating anodes speed them toward the screen.
4. Deflection: Deflection plates/coils (horizontal and vertical) steer the beam to the required $(x,y)$ position on the screen.
5. Light emission: The beam strikes the phosphor coating, which glows at the point of impact, creating a bright spot (pixel).
6. Refresh: Phosphor glow fades, so the image must be redrawn (refreshed) many times per second (e.g. 60 Hz) to avoid flicker. Persistence is the time the phosphor keeps glowing.