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

Scan-Line Polygon Fill Algorithm

This is an image-space, area-filling technique that fills a polygon one horizontal scan line at a time, working from the top scan line to the bottom.

Working principle: For each scan line that crosses the polygon, find the intersection points of the scan line with all polygon edges, sort these x-coordinates in ascending order, pair them up (1st with 2nd, 3rd with 4th, ...) and fill the pixels between each pair. This relies on the fact that a closed polygon is crossed an even number of times by any horizontal line.

Steps:

1. Find $y_{min}$ and $y_{max}$ of the polygon.
2. For each scan line $y$ from $y_{min}$ to $y_{max}$:
   • Compute the x-intersections of the scan line with each edge.
   • Sort the intersections by x.
   • Fill pixels between pairs of intersections.

Edge / vertex handling: Horizontal edges are ignored. If a scan line passes exactly through a vertex, count it once if the two edges meeting at that vertex lie on the same side, and twice if they lie on opposite sides (achieved in practice by shortening the upper edge by one scan line).

For efficiency an Edge Table (ET) and an Active Edge Table (AET) are used. Each AET entry stores $(y_{max}, x_{intersection}, 1/m)$, and as $y$ increases by 1 the x value is incremented by $1/m$ (coherence).

Example: For a triangle with vertices $A(2,2), B(8,2), C(5,8)$, scan line $y=5$ intersects edge $AC$ at $x=3.5$ and edge $BC$ at $x=6.5$. So pixels from $x=4$ to $x=6$ on row $y=5$ are filled. Repeating for all rows fills the whole triangle.

Boundary Fill Algorithm

This is a seed-fill technique used when a region is defined by a boundary of a single specified color. Starting from an interior seed pixel, it recursively colours neighbouring pixels until the boundary color is reached.

4-connected version:

boundaryFill(x, y, fillColor, boundaryColor):
    current = getPixel(x, y)
    if current != boundaryColor and current != fillColor:
        setPixel(x, y, fillColor)
        boundaryFill(x+1, y, fillColor, boundaryColor)
        boundaryFill(x-1, y, fillColor, boundaryColor)
        boundaryFill(x, y+1, fillColor, boundaryColor)
        boundaryFill(x, y-1, fillColor, boundaryColor)

• 4-connected: checks left, right, up, down neighbours. May fail to fill regions that are connected only diagonally.
• 8-connected: also checks the four diagonal neighbours; fills more complex regions but can leak across thin boundaries.

Example: To fill a circle drawn in red (boundary color) with blue, pick an interior seed (e.g. the centre) and call boundaryFill(cx, cy, blue, red). The recursion spreads outward in all directions until every pixel until the red boundary is turned blue.

Comparison: The scan-line method works directly from the polygon's vertex list and is efficient/non-recursive, suited to rendering. Boundary fill works on an already-drawn region in the frame buffer (e.g. interactive paint tools) and is simple but memory-heavy due to recursion.

Bezier Curves

A Bezier curve is a parametric polynomial curve defined by a set of $n+1$ control points $P_0, P_1, \dots, P_n$. For a parameter $u \in [0,1]$ the curve is

where $B_{i,n}(u)$ are the Bernstein basis polynomials

Properties

1. Endpoint interpolation: the curve passes through the first and last control points, $P(0)=P_0$ and $P(1)=P_n$.
2. Tangency: the curve is tangent to $P_0P_1$ at the start and to $P_{n-1}P_n$ at the end.
3. Convex-hull property: the curve lies entirely within the convex hull of its control points.
4. Partition of unity: $\sum_{i=0}^{n} B_{i,n}(u) = 1$, giving affine invariance (transform the curve by transforming control points).
5. Degree: $n$ control points give a curve of degree $n-1$; it is non-local — moving any control point changes the whole curve.
6. Symmetry: reversing the control points gives the same curve traced in the opposite direction.

Derivation: Cubic Bezier Curve (four control points)

For a cubic curve $n = 3$, with control points $P_0, P_1, P_2, P_3$. The Bernstein basis polynomials of degree 3 are:

Therefore

In matrix form:

Verification: $P(0)=P_0$ and $P(1)=P_3$, confirming endpoint interpolation. The derivative gives $P'(0)=3(P_1-P_0)$ and $P'(1)=3(P_3-P_2)$, confirming tangency to the first and last edges of the control polygon.

Bresenham's Line Drawing Algorithm

Bresenham's algorithm draws a line using only integer arithmetic (additions/subtractions and comparisons), avoiding the floating-point operations and rounding of DDA. At each step it chooses the pixel closest to the true line by tracking a decision parameter.

For a line with slope $0 \le m \le 1$ from $(x_0,y_0)$ to $(x_1,y_1)$, let $\Delta x = x_1-x_0$, $\Delta y = y_1-y_0$.

Initial decision parameter: $p_0 = 2\Delta y - \Delta x$

At each step, $x$ increments by 1, and:

• If $p_k < 0$: choose $(x_k+1, y_k)$, and $p_{k+1} = p_k + 2\Delta y$.
• If $p_k \ge 0$: choose $(x_k+1, y_k+1)$, and $p_{k+1} = p_k + 2\Delta y - 2\Delta x$.

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

$\Delta x = 30-20 = 10$, $\Delta y = 18-10 = 8$. Slope $m = 8/10 = 0.8$ (so $0<m<1$, x is the driving axis).

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

Start by plotting $(20, 10)$.

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

The end point $(30,18)$ is reached exactly, confirming the digitization is correct.

Hidden-surface removal methods are classified by the space in which the visibility comparison is performed.

In short, object-space methods determine visibility analytically among objects and are accurate but expensive for complex scenes, whereas image-space methods determine visibility for each pixel of the display and scale better with scene complexity but are limited to screen resolution.

Spline

A spline is a smooth piecewise-polynomial curve that passes through or near a set of given points called control points. The term originates from the flexible strip (also called a spline) draughtsmen used to draw smooth curves through pegs. Mathematically, a spline curve is constructed from polynomial sections joined at points called knots, with continuity conditions ($C^0$, $C^1$, $C^2$ — positional, tangent and curvature continuity) imposed at the joints so the overall curve is smooth.

Interpolation vs Approximation Splines

Summary: If the polynomial sections are fitted so the curve goes through each control point, it is an interpolation spline; if the control points only influence the shape (the curve is pulled toward but generally does not touch them), it is an approximation spline.

Key Frame System in Computer Animation

A key frame is a frame at a specific point in the animation sequence at which the animator explicitly defines the important positions, shapes or states of the objects (the "extremes" of a motion). A key frame system generates the complete animation from a relatively small set of these key frames.

Working principle:

1. The animator (or lead artist) creates the key frames — e.g. frame 1 (start pose) and frame 30 (end pose).
2. The system automatically generates all the in-between frames by interpolating between successive key frames. This automatic generation is called in-betweening or tweening.
3. Interpolation may be linear (constant change per frame) or use non-linear/spline interpolation for smooth acceleration and deceleration (ease-in / ease-out).

Interpolation example: If an object is at position $P_1$ in key frame $k_1$ and $P_2$ in key frame $k_2$, an in-between frame at parameter $t \in [0,1]$ is

Morphing: When the two key frames have different shapes or different numbers of vertices, a transformation called morphing is used to add/adjust vertices so that one object smoothly transforms into the other across the in-between frames.

Advantages: Greatly reduces the animator's workload (only key poses are drawn), and produces smooth, controllable motion. It is the basis of most 2D and 3D animation packages.

Raster Scan Display

In a raster scan display, the electron beam sweeps across the screen one row (scan line) at a time, from top to bottom, covering the entire screen area.

• The picture is stored as a set of intensity/color values for every pixel in a memory area called the frame buffer (refresh buffer).
• As the beam moves along each scan line, its intensity is turned on/off (and colored) according to the corresponding pixel values in the frame buffer.
• After completing the bottom line, the beam returns to the top-left (vertical retrace); after each line it returns to the start of the next line (horizontal retrace).
• The whole screen is refreshed typically 60–80 times per second to avoid flicker.
• Suited to displaying shaded, filled and realistic images (photographs); resolution and quality are limited by frame-buffer size, and lines can show a staircase / aliasing effect.

Random (Vector) Scan Display

In a random/vector scan display the electron beam is directed only to the parts of the screen where a picture is to be drawn, tracing the component lines directly (point-to-point), not pixel-by-pixel.

• The picture is stored as a set of line-drawing commands in an area called the display file / display list, processed by the display processor.
• The beam draws each line segment directly between its endpoints, so lines are smooth with no staircase effect and very high resolution.
• Refresh rate depends on the number of lines (typically 30–60 times/sec); a complex picture with many lines may flicker.
• Best for line drawings, wireframes, engineering and CAD diagrams, but it cannot easily display realistic shaded/filled images.

Key difference: Raster scan refreshes pixel-by-pixel from a frame buffer (good for solid/shaded images); vector scan draws line-by-line from a display list (good for crisp line art).

DDA (Digital Differential Analyzer) Line Drawing Algorithm

DDA is an incremental scan-conversion algorithm that calculates pixel positions along a line by sampling the line at unit intervals along the driving axis and computing the other coordinate using the slope.

For a line from $(x_0,y_0)$ to $(x_1,y_1)$, let $\Delta x = x_1-x_0$, $\Delta y = y_1-y_0$.

Steps:

1. $steps = \max(|\Delta x|, |\Delta y|)$
2. $x_{inc} = \Delta x / steps$, $\quad y_{inc} = \Delta y / steps$
3. Start at $(x,y)=(x_0,y_0)$; plot round(x), round(y).
4. Repeat steps times: $x = x + x_{inc}$, $y = y + y_{inc}$, plot round(x), round(y).

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

Advantages:

• Simpler and faster than the direct line equation $y=mx+c$, since it avoids a multiplication per pixel (uses only additions).
• Easy to understand and implement.

Disadvantages:

• Uses floating-point arithmetic and a round() operation at each step, which is slower than pure integer arithmetic.
• Accumulation of round-off error over a long line can cause the plotted pixels to drift away from the true line.
• Slower than Bresenham's algorithm, which uses only integer operations.

Rotation about an Arbitrary Point in 2D

The basic rotation matrix rotates a point about the origin. To rotate about an arbitrary pivot point $(x_p, y_p)$ by angle $\theta$, 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 to the original pivot: $T(x_p, y_p)$.

Using homogeneous coordinates, the composite matrix is

With

Multiplying these gives

Thus the rotated point is $\begin{bmatrix}x' \\ y' \\ 1\end{bmatrix} = M \begin{bmatrix}x \\ y \\ 1\end{bmatrix}$, i.e.

Sutherland–Hodgman Polygon Clipping Algorithm

This algorithm clips a polygon against a convex clipping window by clipping the entire polygon successively against each of the four window edges (left, right, bottom, top), one edge at a time. The output polygon from one edge becomes the input to the next.

Procedure: For the current clip edge, process each polygon edge defined by consecutive vertices $(S \to E)$ and apply these four cases (output kept vertices in order):

After processing all four window edges, the remaining vertex list is the clipped polygon.

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

• Right edge ($x \le 4$): $A$ inside, $B$ outside $\Rightarrow$ output intersection of $AB$ with $x=4$, which is $(4, 2.5)$. $B$ outside, $C$ inside $\Rightarrow$ output intersection of $BC$ with $x=4$, $(4, 4)$... after processing the new polygon is $A(1,1), (4,2.5), (4,4)\text{-region}, C(2,6)$.
• Top edge ($y \le 4$): clip the result so that any vertex with $y>4$ (e.g. $C(2,6)$) is replaced by the intersection points where the edges cross $y=4$.

Clipping against the remaining edges (left $x\ge0$, bottom $y\ge0$) leaves those vertices unchanged here. The final clipped polygon is the part of the triangle lying inside the rectangle, bounded by the original interior edges and the window edges $x=4$ and $y=4$.

Limitation: Works correctly only for convex clipping windows; for a concave polygon being clipped it may produce extraneous connecting edges (handled better by Weiler–Atherton).

RGB Color Model

The RGB model is an additive color model based on the three primary colors of light: Red, Green, Blue. Colors are produced by adding these primaries in varying intensities; it is represented as a unit cube in Cartesian coordinates.

• Origin $(0,0,0)$ = black; the diagonally opposite corner $(1,1,1)$ = white.
• The main diagonal from black to white represents shades of grey.
• $R+G+B$ at full intensity gives white: $\text{Red}+\text{Green}+\text{Blue} = \text{White}$. Also $R+G=$ Yellow, $G+B=$ Cyan, $R+B=$ Magenta.
• Used by emissive devices: CRT/LED monitors, TV screens, scanners, digital cameras.

CMY Color Model

The CMY model is a subtractive color model based on Cyan, Magenta, Yellow — the complements (secondaries) of RGB. Colors are produced by subtracting light from white (e.g. by pigments/inks on paper that absorb certain wavelengths).

• $(0,0,0)$ = white (no ink); $(1,1,1)$ = black (all inks).
• $C+M+Y$ subtracts all light to give black.
• Used by reflective devices: printers and hard-copy/plotting devices. (In practice CMYK adds a separate black ink K for richer blacks.)

Relationship

RGB and CMY are complementary. The conversion is simply:

In short: RGB is additive (light, displays, black at origin), CMY is subtractive (pigment, printing, white at origin).

3D Transformation Matrices (Homogeneous Coordinates)

A point is represented as $[x\ y\ z\ 1]^T$ and transformed by a $4\times4$ matrix.

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

Gives $x'=x+t_x,\ y'=y+t_y,\ z'=z+t_z$.

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

Gives $x'=s_x x,\ y'=s_y y,\ z'=s_z z$ (scaling is about the origin).

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

The $x$-coordinate is unchanged; the $y$ and $z$ coordinates rotate.

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

(Positive $\theta$ follows the right-hand rule looking from $+x$ toward the origin.)