3. Scan Conversion / Drawing Algorithms

Scan conversion is the process of converting ideal geometric primitives (lines, circles, polygons defined in continuous mathematical space) into discrete pixels on a raster display. The core challenge is deciding which pixels best approximate the mathematical object while minimizing computation and visual error.

Every drawing algorithm is a trade-off between accuracy, speed, and hardware efficiency. Raster graphics demand integer, incremental decisions rather than continuous equations.

            flowchart LR
                Math[Continuous Mathematical Line] --> Sampling[Sampling/Scan Conversion]
                Sampling --> Discrete[Discrete Pixels]
                Discrete --> Display[Raster Display]
            

3.1 Line Drawing Algorithms

A line is mathematically infinite and continuous, but a screen is a finite grid of pixels. Line drawing algorithms decide pixel-by-pixel placement to approximate the ideal line between two endpoints.

3.1.1 DDA Algorithm (Digital Differential Analyzer)

DDA is a simple incremental line-generation algorithm based on the slope of the line. It works by sampling intermediate points between two endpoints using floating-point arithmetic.

Core idea: Move in small steps along the dominant axis and compute the corresponding coordinate using the line equation.

Given two endpoints:

$$ (x_1, y_1), (x_2, y_2) $$

Compute differences:

$$ \Delta x = x_2 - x_1 $$

$$ \Delta y = y_2 - y_1 $$

Slope:

$$ m = \frac{\Delta y}{\Delta x} $$

• Dominant axis: The axis along which movement is uniform.
• Incremental nature: Each step depends on the previous one.

3.1.1.1 Case: |m| < 1

When the slope magnitude is less than 1, the line is more horizontal than vertical.

Strategy:

• Increment x by 1 unit
• Increment y by m

Recurrence relation:

$$ x_{k+1} = x_k + 1 $$

$$ y_{k+1} = y_k + m $$

Each computed y is rounded to the nearest integer pixel.

3.1.1.2 Case: |m| > 1

When the slope magnitude is greater than 1, the line is steeper.

Strategy:

• Increment y by 1 unit
• Increment x by $1/m$

Recurrence relation:

$$ y_{k+1} = y_k + 1 $$

$$ x_{k+1} = x_k + \frac{1}{m} $$

3.1.1.3 Drawbacks of DDA

• Uses floating-point arithmetic → slow on early hardware
• Rounding errors accumulate
• Less efficient compared to integer-based algorithms

DDA is conceptually important but rarely used in performance-critical systems.

Worked Examples: DDA Line Drawing Algorithm

The following solved problems demonstrate how the DDA algorithm incrementally generates pixel positions between two endpoints. Each example explicitly shows slope calculation, dominant axis selection, incremental updates, and rounding — exactly as expected in university examinations.

Example 1: Line from (2, 3) to (12, 8)

Step 1: Given endpoints

$$ (x_1, y_1) = (2, 3), \quad (x_2, y_2) = (12, 8) $$

Step 2: Compute differences

$$ \Delta x = 12 - 2 = 10 $$

$$ \Delta y = 8 - 3 = 5 $$

Step 3: Compute slope

$$ m = \frac{\Delta y}{\Delta x} = \frac{5}{10} = 0.5 $$

Since $|m| < 1$, increment x by 1 each step.

Step 4: Initial point

$$ (x_0, y_0) = (2, 3) $$

Step 5: Incremental equations

$$ x_{k+1} = x_k + 1 $$

$$ y_{k+1} = y_k + m = y_k + 0.5 $$

Step 6: Compute pixel positions (rounded)

Example 2: Line from (20, 10) to (30, 18)

Step 1: Endpoints

$$ (20, 10), (30, 18) $$

Step 2: Differences

$$ \Delta x = 30 - 20 = 10 $$

$$ \Delta y = 18 - 10 = 8 $$

Step 3: Slope

$$ m = \frac{8}{10} = 0.8 $$

Since $|m| < 1$, x is incremented.

Step 4: Initial point

$$ (x_0, y_0) = (20, 10) $$

Step 5: Increment equations

$$ x_{k+1} = x_k + 1 $$

$$ y_{k+1} = y_k + 0.8 $$

Step 6: Raster points

Example 3: Line from (1, 1) to (4, 9)

Step 1: Endpoints

$$ (1, 1), (4, 9) $$

Step 2: Differences

$$ \Delta x = 4 - 1 = 3 $$

$$ \Delta y = 9 - 1 = 8 $$

Step 3: Slope

$$ m = \frac{8}{3} \approx 2.67 $$

Since $|m| > 1$, increment y by 1 each step.

Step 4: Initial point

$$ (x_0, y_0) = (1, 1) $$

Step 5: Increment equations

$$ y_{k+1} = y_k + 1 $$

$$ x_{k+1} = x_k + \frac{1}{m} = x_k + 0.375 $$

Step 6: Raster points

3.1.2 Bresenham’s Line Algorithm

Bresenham’s algorithm improves upon DDA by eliminating floating-point arithmetic entirely. It uses integer calculations and a decision parameter to choose between candidate pixels.

Key insight: At each step, choose the pixel whose center is closest to the ideal line.

Assume:

• $0 \le m \le 1$
• Line drawn left to right

Compute:

$$ \Delta x = x_2 - x_1 $$

$$ \Delta y = y_2 - y_1 $$

3.1.2.1 Decision Parameter

The decision parameter $P_k$ determines whether the next pixel is chosen directly east (E) or north-east (NE).

Initial decision parameter:

$$ P_0 = 2\Delta y - \Delta x $$

Decision rule:

• If $P_k < 0$: choose E
• If $P_k \ge 0$: choose NE

3.1.2.2 Update Equations

If E is chosen:

$$ P_{k+1} = P_k + 2\Delta y $$

If NE is chosen:

$$ P_{k+1} = P_k + 2(\Delta y - \Delta x) $$

All operations are integer-based, making the algorithm fast and precise.

Worked Examples: Bresenham’s Line Drawing Algorithm

The following solved problems demonstrate the complete application of Bresenham’s Line Algorithm using integer arithmetic. Each example explicitly shows the computation of the decision parameter $P_k$, the choice of pixel (E or NE), and the updated value of $P_k$ at every step, exactly in the form expected in examinations.

Example 1: Line from (20, 10) to (30, 18)

Step 1: Given endpoints

$$ (x_1, y_1) = (20, 10), \quad (x_2, y_2) = (30, 18) $$

Step 2: Compute differences

$$ \Delta x = 30 - 20 = 10 $$

$$ \Delta y = 18 - 10 = 8 $$

Step 3: Check slope

$$ m = \frac{\Delta y}{\Delta x} = \frac{8}{10} = 0.8 $$

Since $0 \le m \le 1$, standard Bresenham formulation is used (increment x each step).

Step 4: Initial decision parameter

$$ P_0 = 2\Delta y - \Delta x = 2(8) - 10 = 6 $$

Step 5: Decision rules

• If $P_k < 0$ → choose East (E)
• If $P_k \ge 0$ → choose North-East (NE)

Step 6: Rasterization steps

Example 2: Line from (2, 3) to (12, 8)

Step 1: Endpoints

$$ (2, 3), (12, 8) $$

Step 2: Differences

$$ \Delta x = 10, \quad \Delta y = 5 $$

Step 3: Slope check

$$ m = \frac{5}{10} = 0.5 $$

Step 4: Initial decision parameter

$$ P_0 = 2(5) - 10 = 0 $$

Step 5: Rasterization

Example 3: Line from (5, 5) to (13, 9)

Step 1: Endpoints

$$ (5, 5), (13, 9) $$

Step 2: Differences

$$ \Delta x = 8 $$

$$ \Delta y = 4 $$

Step 3: Initial decision parameter

$$ P_0 = 2(4) - 8 = 0 $$

Step 4: Raster positions

3.2 Circle Drawing Algorithms

Circles are symmetric geometric shapes, which allows optimization by computing points in one region and reflecting them across axes.

3.2.1 Mid-Point Circle Algorithm

This algorithm determines the points of a circle using incremental integer calculations and exploits 8-way symmetry.

Circle equation:

$$ x^2 + y^2 = r^2 $$

Only the first octant is computed:

• $x \ge 0$
• $y \ge x$

3.2.1.1 Decision Parameter

Initial decision parameter:

$$ P_0 = 1 - r $$

This determines whether the midpoint lies inside or outside the circle.

3.2.1.2 Update Rules

If $P_k < 0$ (midpoint inside circle):

$$ P_{k+1} = P_k + 2x + 3 $$

If $P_k \ge 0$ (midpoint outside circle):

$$ P_{k+1} = P_k + 2(x - y) + 5 $$

After computing one octant, reflect points to obtain the full circle.

Worked Examples: Mid-Point Circle Algorithm

The following solved problems illustrate the application of the Mid-Point Circle Algorithm. Each example explicitly shows symmetry usage, decision parameter calculation, and step-by-step pixel generation, exactly aligned with university examination expectations.

Example 1: First 8 Symmetric Points for a Circle of Radius r = 6

Given

Center: $$ (0,0) $$

Radius: $$ r = 6 $$

Step 1: Starting point

The Mid-Point Circle Algorithm always starts at:

$$ (x_0, y_0) = (0, r) = (0, 6) $$

Step 2: 8-way symmetry rule

For any computed point $(x, y)$, the corresponding symmetric points are:

• $( x, y)$
• $( y, x)$
• $(-x, y)$
• $(-y, x)$
• $(-x, -y)$
• $(-y, -x)$
• $( x, -y)$
• $( y, -x)$

Step 3: First 8 symmetric points

Using $(0, 6)$:

This demonstrates how a single computed point generates the full circle using symmetry.

Example 2: First Quadrant Pixels for r = 10, Center (0,0)

Step 1: Given

$$ r = 10, \quad (x_c, y_c) = (0,0) $$

Step 2: Initial values

$$ x_0 = 0, \quad y_0 = 10 $$

Initial decision parameter:

$$ P_0 = 1 - r = 1 - 10 = -9 $$

Step 3: Decision rules

• If $P_k < 0$ → choose East (E): $x_{k+1}=x_k+1$
• If $P_k \ge 0$ → choose South-East (SE): $x_{k+1}=x_k+1, y_{k+1}=y_k-1$

Step 4: Iterations (First Quadrant)

These points define the first quadrant arc; remaining points are obtained using symmetry.

Example 3: Initial Decision Parameter and First 3 Pixels for r = 14

Given

Center: $$ (0,0) $$

Radius: $$ r = 14 $$

Step 1: Initial point

$$ (x_0, y_0) = (0, 14) $$

Step 2: Initial decision parameter

$$ P_0 = 1 - r = 1 - 14 = -13 $$

Step 3: Iteration 1

$P_0 < 0$ → choose E

$$ (x_1, y_1) = (1, 14) $$

$$ P_1 = -13 + 2(0) + 3 = -10 $$

Step 4: Iteration 2

$P_1 < 0$ → choose E

$$ (x_2, y_2) = (2, 14) $$

$$ P_2 = -10 + 2(1) + 3 = -5 $$

Step 5: Iteration 3

$P_2 < 0$ → choose E

$$ (x_3, y_3) = (3, 14) $$

$$ P_3 = -5 + 2(2) + 3 = 2 $$

First 3 pixel positions

• $(0, 14)$
• $(1, 14)$
• $(2, 14)$

3.3 Polygon Filling

Polygon filling determines which pixels lie inside a closed boundary. It is essential for rendering solid objects.

3.3.1 Scan-Line Fill Algorithm

The scan-line algorithm processes the polygon one horizontal scan line at a time.

Procedure:

• Intersect scan line with polygon edges
• Sort intersection points by x-coordinate
• Fill pixels between pairs of intersections

3.3.1.1 Odd-Even Rule (Parity Rule)

Count intersections from left to right:

• Odd count → inside
• Even count → outside

This rule is simple and widely used.

3.3.1.2 Non-Zero Winding Rule

Each edge contributes a direction:

• Upward crossing: +1
• Downward crossing: −1

If total winding number ≠ 0, the point lies inside the polygon.

This handles complex and self-intersecting polygons accurately.

3.4 Aliasing and Antialiasing

Aliasing occurs when a continuous signal is sampled too coarsely, producing jagged edges (jaggies).

Cause:

• Insufficient sampling resolution
• High-frequency detail mapped to low-resolution grids

Antialiasing reduces these artifacts by smoothing intensity transitions.

• Supersampling: sample at higher resolution
• Area sampling: weight pixel coverage
• Filtering: remove high-frequency components

Antialiasing trades computational cost for visual quality.

Algorithm Breakdown

• Scan Conversion: Process of digitizing continuous geometric primitives (lines/circles) into discrete pixels.
• DDA Algorithm: Uses slope \(m\); if \(|m| \le 1\), increment \(x\) by 1, \(y\) by \(m\); suffers from floating-point overhead and rounding errors.
• Bresenham’s Line Algorithm: Uses extensive integer arithmetic and a decision parameter (\(p\)) to select the closest pixel (E or NE), optimizing speed.
• Mid-Point Circle Algorithm: Exploits 8-way symmetry; computes one octant using decision parameter \(p = 1 - r\) to keep/change direction.
• Scan-Line Fill: Fills polygons by intersecting scan lines with edges and filling spans between intersection pairs.
• Odd-Even Rule: Determines interior points; count intersections from infinity to point (odd = inside, even = outside).
• Aliasing: Jagged edges ("jaggies") caused by low-resolution sampling; mitigated by Antialiasing techniques (Supersampling, Filtering).