Unit 3

Line Drawing Algorithm

DDA Line Drawing Algorithm

The DDA (Digital Differential Analyzer) line drawing algorithm is an efficient method for drawing lines in computer graphics. It uses simple calculations to determine the coordinates of each pixel along a line.

Steps to Draw a Line using DDA Algorithm

Step 1: Given Two Points
We are given two points, which define the start and end of the line:
- Point 1 (x1, y1) – Start point of the line.
- Point 2 (x2, y2) – End point of the line.
The points (x1, y1) and (x2, y2) will define the start and end of the line.
Step 2: Calculate Differences
We calculate the differences in the X and Y coordinates:

\[ \Delta X = x2 - x1 \]

\[ \Delta Y = y2 - y1 \]

The values of ΔX and ΔY will help in determining the slope and how to increment X or Y.
Step 3: Calculate the Slope
The slope (m) of the line is calculated as:

\[ m = \frac{\Delta Y}{\Delta X} \]

This gives us the direction of the line, which helps in deciding whether to increment X or Y.
Step 4: Decide Whether to Increment X or Y
Now, we decide how to move along the line. There are two cases:
- Case 1: When ΔX ≥ ΔY (X changes more than Y)
  In this case, we increment X by 1 in each step. To find the corresponding Y, we use the slope:
  
  \[ \Delta Y = m \times \Delta X \]
  
  Since we are incrementing X by 1 (i.e., ΔX = 1), we substitute this into the equation:
  
  \[ y_{i+1} = y_i + m \]
  
  Now, we increment X by 1:
  
  \[ x_{i+1} = x_i + 1 \]
- Case 2: When ΔY > ΔX (Y changes more than X)
  In this case, we increment Y by 1 in each step. To find the corresponding X, we rearrange the slope formula:
  
  \[ \Delta X = \frac{\Delta Y}{m} \]
  
  Since we are incrementing Y by 1 (i.e., ΔY = 1), we substitute this into the equation:
  
  \[ x_{i+1} = x_i + \frac{1}{m} \]
  
  Now, we increment Y by 1:
  
  \[ y_{i+1} = y_i + 1 \]
Step 5: Continue Until the End Point is Reached
Start at (x1, y1) and keep calculating the next coordinates using the steps above until reaching (x2, y2). Round the values to get the closest integer pixel positions.

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

Given:

Point 1 (x1, y1) = (2, 3)
Point 2 (x2, y2) = (6, 8)

First, calculate the differences:

\[ \Delta X = 6 - 2 = 4, \quad \Delta Y = 8 - 3 = 5 \]

Next, calculate the slope:

\[ m = \frac{5}{4} = 1.25 \]

Since ΔY > ΔX, we increment Y by 1 and calculate X for each step. Here’s the calculation for the points:

Start at (2, 3).
Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 2 + \frac{1}{1.25} = 2.8 \]

The next point is (2.8, 4).
Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 2.8 + \frac{1}{1.25} = 3.6 \]

The next point is (3.6, 5).
Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 3.6 + \frac{1}{1.25} = 4.4 \]

The next point is (4.4, 6).
Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 4.4 + \frac{1}{1.25} = 5.2 \]

The next point is (5.2, 7).
Final point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 5.2 + \frac{1}{1.25} = 6 \]

The next point is (6, 8), which is the end point.

Here’s the table of values:

                    
  x   |  y
------+------
  2   |  3
  2.8 |  4
  3.6 |  5
  4.4 |  6
  5.2 |  7
  6   |  8

This table shows the calculated points from the start to the end point using the DDA algorithm.

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

Given:

Point 1 (x1, y1) = (1, 1)
Point 2 (x2, y2) = (4, 3)

First, calculate the differences:

\[ \Delta X = 4 - 1 = 3, \quad \Delta Y = 3 - 1 = 2 \]

Next, calculate the slope:

\[ m = \frac{2}{3} \approx 0.6667 \]

Since ΔX > ΔY, we increment X and calculate Y for each step. Here’s the calculation for the points:

Start at (1, 1).
Next point: Increment X by 1, calculate Y:

\[ Y_{\text{next}} = Y + m = 1 + 0.6667 = 1.6667 \]

The next point is (2, 1.6667).
Next point: Increment X by 1, calculate Y:

\[ Y_{\text{next}} = Y + m = 1.6667 + 0.6667 = 2.3333 \]

The next point is (3, 2.3333).
Final point: Increment X by 1, calculate Y:

\[ Y_{\text{next}} = Y + m = 2.3333 + 0.6667 = 3 \]

The next point is (4, 3), which is the end point.

Here’s the table of values:

                    
  x  |	y
-----+-----
  1  |	1
  2  |	1.6667
  3  |	2.3333
  4  |	3

This table shows the calculated points from the start to the end point using the DDA algorithm.

Bresenham's Line Drawing Algorithm

We are familiar with the DDA (Digital Differential Analyzer) algorithm for line drawing, right? It works by calculating the slope of the line and incrementing the coordinates in steps, using floating-point arithmetic. While DDA provides a simple and straightforward way to draw lines, the main drawback is that it uses floating-point calculations, which can lead to rounding errors and less efficient performance.
This is where Bresenham's Line Drawing Algorithm comes in. Unlike DDA, which uses floating-point calculations, Bresenham's algorithm works entirely with integer arithmetic. This means it avoids the use of floating-point numbers, leading to more accurate and efficient calculations. The result is a much faster and more precise way to draw lines on digital screens, without the risk of rounding errors.

Definition: The Bresenham's Line Drawing Algorithm is an efficient way to draw a straight line between two points in computer graphics. The algorithm uses integer calculations to avoid the use of floating-point operations, making it faster and suitable for raster display systems.

Step 1: Given Two Points
We are given two points (x1, y1) and (x2, y2), which define the start and end of the line.
Step 2: Calculate Differences
First, we calculate the differences in X and Y:

\[ \Delta X = x2 - x1, \quad \Delta Y = y2 - y1 \]

Important: These values of ΔX and ΔY are calculated once at the beginning and remain the same throughout the algorithm. When updating the decision parameter p, we always use these initial values and do not recalculate them based on the updated x and y.
Step 3: Calculate the Slope
The slope m is calculated as:

\[ m = \frac{\Delta Y}{\Delta X} \]

We use this to determine whether the line is shallow or steep.
Step 4: Initialize the Decision Parameter
The decision parameter p is initialized using the fixed values of ΔX and ΔY:

\[ p = 2\Delta Y - \Delta X \]

Important: When updating p in later steps, we always use the original ΔX and ΔY that were calculated at the beginning.
Step 5: Check the Slope
Now, we check whether the slope m is less than 1 or greater than or equal to 1. The algorithm behaves differently based on this value:
- Case 1: When m < 1 (Shallow Line - More Horizontal)
  If m < 1, we always increment x by 1 and decide whether to increment y.
  
  Using the fixed values of ΔX and ΔY, the steps are:
  - Start: Let x0 = x1 and y0 = y1. We continue until we reach x2.
  - If p < 0:
    \[ x_{i+1} = x_i + 1, \quad y_{i+1} = y_i \]
    
    Update p using the fixed ΔX and ΔY:
    
    \[ p = p + 2 \Delta Y \]
  - If p ≥ 0:
    \[ x_{i+1} = x_i + 1, \quad y_{i+1} = y_i + 1 \]
    
    Update p using the fixed ΔX and ΔY:
    
    \[ p = p + 2 \Delta Y - 2 \Delta X \]
- Case 2: When m ≥ 1 (Steep Line - More Vertical)
  If m ≥ 1, we always increment y by 1 and decide whether to increment x.
  
  Using the fixed values of ΔX and ΔY, the steps are:
  - Start: Let x0 = x1 and y0 = y1. We continue until we reach y2.
  - If p < 0:
    \[ x_{i+1} = x_i, \quad y_{i+1} = y_i + 1 \]
    
    Update p using the fixed ΔX and ΔY:
    
    \[ p = p + 2 \Delta X \]
  - If p ≥ 0:
    \[ x_{i+1} = x_i + 1, \quad y_{i+1} = y_i + 1 \]
    
    Update p using the fixed ΔX and ΔY:
    
    \[ p = p + 2 \Delta X - 2 \Delta Y \]
Step 6: Continue Until the End Point is Reached
We continue applying the rules above, updating p and plotting the points step by step from (x1, y1) to (x2, y2).

Important: The values of ΔX and ΔY never change during this process. When updating p, we do not recalculate them using the new x and y. Instead, we always use the original values calculated at the beginning.

Bresenham's Line Drawing Algorithm: Example

We will use Bresenham's Line Drawing Algorithm to draw a line between the points (1, 1) and (5, 3).

Given Two Points:

Let the starting point be:

\[ x_0 = 1, \quad y_0 = 1 \]

We continue until we reach:

\[ x = 5, \quad y = 3 \]

Step 1: Calculate Differences

First, we calculate the differences in the x and y coordinates:

\[ \Delta X = x_2 - x_1 = 5 - 1 = 4, \quad \Delta Y = y_2 - y_1 = 3 - 1 = 2 \]

Step 2: Compute Initial Decision Parameter

The decision parameter \( p \) is calculated as:

\[ p_0 = 2 \Delta Y - \Delta X = 2 \times 2 - 4 = 0 \]

Step 3: Iterating Through Points

Since \( m < 1 \), we increment \( x \) by 1 at each step and decide whether to increment \( y \) based on \( p \).

Initially: \( x_0 = 1, y_0 = 1, p_0 = 0 \).
Step 1: Since \( p_0 \geq 0 \), we increment both \( x \) and \( y \):

\[ x_1 = x_0 + 1 = 2, \quad y_1 = y_0 + 1 = 2 \]

Update \( p \):

\[ p_1 = p_0 + 2 \Delta Y - 2 \Delta X = 0 + 2(2) - 2(4) = -4 \]

Step 2: Since \( p_1 < 0 \), we only increment \( x \):

\[ x_2 = x_1 + 1 = 3, \quad y_2 = y_1 = 2 \]

Update \( p \):

\[ p_2 = p_1 + 2 \Delta Y = -4 + 2(2) = 0 \]

Step 3: Since \( p_2 \geq 0 \), we increment both \( x \) and \( y \):

\[ x_3 = x_2 + 1 = 4, \quad y_3 = y_2 + 1 = 3 \]

Update \( p \):

\[ p_3 = p_2 + 2 \Delta Y - 2 \Delta X = 0 + 2(2) - 2(4) = -4 \]

Step 4: Since \( p_3 < 0 \), we only increment \( x \):

\[ x_4 = x_3 + 1 = 5, \quad y_4 = y_3 = 3 \]

Since we have reached \( x = 5, y = 3 \), we stop.

Table of Calculated Points:

    
  X  | Y  | p  | Action
-----+----+----+----------------------------
  1  | 1  |  0  | Initial point
  2  | 2  | -4  | Increment X, Increment Y (p ≥ 0)
  3  | 2  |  0  | Increment X only (p < 0)
  4  | 3  | -4  | Increment X, Increment Y (p ≥ 0)
  5  | 3  |  -  | Increment X only, reached endpoint

The points (1,1), (2,2), (3,2), (4,3), and (5,3) are plotted following Bresenham's algorithm. The decision parameter is used to determine whether to increment Y in each step while always incrementing X by 1.

Midpoint Circle Drawing Algorithm (Mathematical Approach)

The Midpoint Circle Algorithm is an efficient method for drawing circles using only integer calculations. It avoids floating-point arithmetic, making it faster for computers.

Why Do We Need This Algorithm?

A circle is defined by the equation:

\[ x^2 + y^2 = r^2 \]

However, solving for \( y \) requires square roots and floating-point calculations, which are inefficient. The Midpoint Circle Algorithm helps determine the next pixel using integer calculations only.

Steps to Draw a Circle using the Midpoint Algorithm

Step 1: Start from (0, r) and Consider the Next Point
We start at \( (0, r) \), the top of the circle (90°), and move towards the 45° line.

At each step, we have two possible choices for the next pixel:
- Move right → \( (x+1, y) \)
- Move diagonally down-right → \( (x+1, y-1) \)
We need a way to decide which point is closer to the actual circle.
Step 2: Define the Midpoint Decision Parameter
To make this decision, we use the midpoint between the two possible points:

\[ \text{Midpoint} = (x+1, y - \frac{1}{2}) \]

We check whether this midpoint is inside or outside the circle to decide the next point.
Step 3: Using the Circle Equation to Check the Midpoint
The equation of a circle is:

\[ x^2 + y^2 - r^2 = 0 \]

For the midpoint, we define the decision parameter:

\[ p = f(x+1, y - \frac{1}{2}) = (x+1)^2 + (y - \frac{1}{2})^2 - r^2 \]

To avoid fractions, we multiply everything by 2 and simplify. The initial decision parameter at \( (0, r) \) is:

\[ p = 1 - r \]
Step 4: Decision Making and Updating \( p \)
At each step, we check the midpoint \( (x+1, y - \frac{1}{2}) \) using the decision parameter \( p \).
- Case 1: If \( p < 0 \) (Midpoint is inside the circle) → Move Right
  Since the midpoint is inside the circle, the actual circle passes above it, so we move right to \( (x+1, y) \).
  
  We update the decision parameter:
  
  \[ p_{\text{new}} = p + 2x + 3 \]
- Case 2: If \( p \geq 0 \) (Midpoint is outside or on the circle) → Move Diagonally Down-Right
  Since the midpoint is outside the circle, the actual circle passes below it, so we move diagonally to \( (x+1, y-1) \).
  
  We update the decision parameter:
  
  \[ p_{\text{new}} = p + 2x - 2y + 5 \]
Step 5: Stopping Condition – When Do We Stop?
We start at \( (0, r) \) (top of the circle at 90°) and move downward until we reach the 45° line.

We stop when:

\[ x \geq y \]

This happens because:
- At \( x = 0, y = r \), the point is at the top of the circle.
- As \( x \) increases and \( y \) decreases, the points curve toward the right.
- When \( x = y \), we reach exactly 45° (the diagonal line).
- Beyond this point, values will mirror the already-calculated points.
Why Are We Calculating Only 1/8th of the Circle?
We calculate only 1/8th of the circle because:
- We start at \( (0, r) \), which is at 90° (topmost point).
- We compute points until \( x = y \), which is exactly 45°.
- The rest of the circle is drawn using symmetry.
By using symmetry, we save computation time and ensure efficient drawing of the full circle.

Example: Draw a Circle with Center (0,0) and Radius 5

Step 1: Given Information

Center of the Circle: \( (0,0) \)
Radius: \( r = 5 \)

Step 2: Initial Setup

We start from the topmost point of the circle at \( (0,5) \). The decision parameter helps us determine the next point.

Step 3: Compute Initial Decision Parameter

The initial decision parameter is given by:

\[ p_0 = 1 - r \]

Substituting \( r = 5 \):

\[ p_0 = 1 - 5 = -4 \]

Step 4: Compute Points Step by Step

We use the decision rule:

If \( p_k < 0 \): Next point is \( (x+1, y) \), update \( p \) using:
\[ p_{\text{new}} = p + 2x + 3 \]
If \( p_k \geq 0 \): Next point is \( (x+1, y-1) \), update \( p \) using:
\[ p_{\text{new}} = p + 2x - 2y + 5 \]

Step-by-Step Calculations

Starting from \( (0,5) \):

Step 1: We start with \( p_0 = -4 \), which is calculated using the formula \( p_0 = 1 - r \) where \( r = 5 \).
At this point, the current values of \( x = 0 \) and \( y = 5 \). Since \( p_0 < 0 \), we move horizontally to the right, meaning the next point will be \( (x+1, y) = (1, 5) \), and we update the decision parameter:

\( p_1 = p_0 + 2x + 3 = -4 + 2(0) + 3 = -1 \)
Step 2: Now we have \( p_1 = -1 \), and the current values of \( x = 1 \) and \( y = 5 \). Since \( p_1 < 0 \), we again move horizontally to the right, meaning the next point will be \( (x+1, y) = (2, 5) \). We update the decision parameter:

\( p_2 = p_1 + 2x + 3 = -1 + 2(1) + 3 = 4 \)
Step 3: Now we have \( p_2 = 4 \), and the current values of \( x = 2 \) and \( y = 5 \). Since \( p_2 \geq 0 \), we move diagonally, meaning the next point will be \( (x+1, y-1) = (3, 4) \). We then update the decision parameter:

\( p_3 = p_2 + 2x - 2y + 5 = 4 + 2(2) - 2(5) + 5 = 3 \)
Step 4: Now we have \( p_3 = 3 \), and the current values of \( x = 3 \) and \( y = 4 \). Since \( p_3 \geq 0 \), we again move diagonally, meaning the next point will be \( (x+1, y-1) = (4, 3) \). However, since \( x = 4 \) and \( y = 3 \), we stop the algorithm here as the condition \( x \geq y \) is satisfied (we have completed one-eighth of the circle).

Final Points

                    
  x  |  y
-----+-----
  0  |  5
  1  |  5
  2  |  5
  3  |  4
  4  |  3

These points are calculated for one-eighth of the circle.