Computer Graphics Chapter 2: The Art and Science of Line Drawing Algorithms

Computer Graphics Chapter 2: Line Drawing Algorithms

Computer Graphics Fundamentals: Line Drawing Algorithms - DDA vs. Bresenham's

Polynomial Method Line Drawing in Computer Graphics | How to Draw Line using DDA algorithm in CG 🎮04

Welcome back, graphics enthusiasts! Professor Dr. Zeeshan Bhatti here from Zeeshan Academy. Today, we're tackling one of the most fundamental problems in computer graphics: how to draw a straight line on a pixel-based screen.

This might seem trivial at first glance. After all, we've been drawing lines since kindergarten. However, in the digital realm, where everything is composed of discrete pixels, drawing a perfect, smooth line requires some clever mathematics. The solutions to this problem, known as Line Drawing Algorithms, are the unsung heroes behind every digital image, user interface, and video game. Let's explore the two most famous ones: the Digital Differential Analyzer (DDA) and the mighty Bresenham's Algorithm.

The Core Challenge: From Continuous to Discrete

Before we dive into the algorithms, let's understand the problem. A mathematical line is continuous and infinitely thin. Our computer screen, however, is a grid of discrete pixels. The challenge is to determine which pixels to "turn on" to best approximate this ideal line.

The goal is twofold:

1. Accuracy: The lit pixels should form a path that is as close as possible to the true line.

2. Efficiency: The calculation must be fast, as modern images require drawing millions of such primitives.

---

Algorithm 1: The Digital Differential Analyzer (DDA)

The DDA algorithm is a straightforward, intuitive approach based on the simple concept of the slope of a line.

The Mathematical Foundation

Given two endpoints of a line, $(x_0,y_0)$ and $(x_1,y_1)$, the slope $m$ is defined as:

$$m=\frac{y_1-y_0}{x_1-x_0}=\frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}$$

From this, we get two key relationships:

$$\mathrm{\Delta }y=m\cdot \mathrm{\Delta }x$$$$\mathrm{\Delta }x=\frac{1}{m}\cdot \mathrm{\Delta }y$$

The brilliance of DDA lies in its incremental approach. Instead of calculating the y-coordinate for every x from scratch, we start at one point and use the slope to find the next point.

The DDA Algorithm Step-by-Step

Step 1: Plot the first pixel at the starting point $(x,y)=(x_0,y_0)$.

Step 2: Calculate the increments. Since pixels are a unit distance apart, we can take a step of 1 in either the x or y direction and calculate the corresponding change in the other.

• If $\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid }>\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid }$ (a shallow line), take steps of 1 in the x-direction.

  • $dx=1$

  • $dy=m$

• If $\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid }>\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid }$ (a steep line), take steps of 1 in the y-direction.

  • $dx=\frac{1}{m}$

  • $dy=1$

Step 3: At each step, increment the current position by $dx$ and $dy$ to get the next pixel.

$$x_{\text{new}}=x_{\text{old}}+dx$$$$y_{\text{new}}=y_{\text{old}}+dy$$

Plot the pixel at $(round(x_{\text{new}}),round(y_{\text{new}}))$.

Step 4: Continue this process until you reach the final endpoint $(x_1,y_1)$.

Pros and Cons of DDA:

• Pro: It's simple to understand and implement.

• Con: It uses floating-point operations (like calculating $m$ and $dy$), which are computationally expensive for a computer. It also requires rounding off at each step, which can accumulate error.

---

Algorithm 2: Bresenham's Line Generation Algorithm

Now, let's meet the champion of line drawing. Bresenham's algorithm is a masterpiece of efficiency because it uses only integer calculations, making it significantly faster than DDA.

The Core Insight

Bresenham's algorithm is also an incremental algorithm. As we move across the x-axis in unit intervals, we have a simple binary choice at each step: which of the two possible y-coordinates is closer to the true line?

For example, from a starting pixel at (2, 3), the next x-coordinate is 3. But should we plot the pixel at (3, 3) or (3, 4)? Bresenham's algorithm uses a decision parameter to make this choice efficiently.

At each step, the algorithm chooses between the pixel to the East (E) or the North-East (NE) based on which is closer to the true line.

Bresenham Line Drawing Algorithm in Computer Graphics | Solving Bresenham Line Algorithm 🎮05

Deriving the Bresenham's Algorithm (For |m| < 1)

Let's assume we are at a pixel $P(x_i,y_i)$. The true y-value of the line at $x_{i+1}$ is $y$.

We have two candidate pixels for the next position:

• $E(x_i+1,y_i)$ - the East pixel

• $NE(x_i+1,y_i+1)$ - the North-East pixel

Let $d_1$ and $d_2$ be the vertical distances from the true line to the candidates E and NE, respectively.

$$d_1=y-y_i$$$$d_2=(y_i+1)-y$$

The decision is simple: if $d_1$ is smaller, choose E; if $d_2$ is smaller, choose NE. Instead of comparing $d_1$ and $d_2$ directly (which would require floating-point math), we define a decision parameter $p_i$ that can be computed using integers only.

The key is to analyze the difference:

$$d_1-d_2=(y-y_i)-((y_i+1)-y)=2y-2y_i-1$$

Now, we substitute the equation of the line. The line equation is $y=mx+b$, and we know $m=\frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}$. Substituting gives:

$$p_i=\mathrm{\Delta }x(d_1-d_2)=\mathrm{\Delta }x(2\cdot \frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}\cdot (x_i+1)+2b-2y_i-1)$$

After simplification, this resolves to an integer-only expression:

$$p_i=2\mathrm{\Delta }y\cdot x_i-2\mathrm{\Delta }x\cdot y_i+c$$

Where $c$ is a constant. The beauty is in the incremental update. We can find $p_{i+1}$ in terms of $p_i$:

• If we choose E (y doesn't change):

  $$p_{i+1}=p_i+2\mathrm{\Delta }y$$

• If we choose NE (y increases by 1):

  $$p_{i+1}=p_i+2\mathrm{\Delta }y-2\mathrm{\Delta }x$$

The initial decision parameter $p_0$ is also an integer: $p_0=2\mathrm{\Delta }y-\mathrm{\Delta }x$.

The Bresenham's Algorithm (for |slope| < 1):

1. Input endpoints $(x_0,y_0)$ and $(x_1,y_1)$.

2. Calculate $\mathrm{\Delta }x=x_1-x_0$, $\mathrm{\Delta }y=y_1-y_0$.

3. Compute the initial decision parameter $p=2\mathrm{\Delta }y-\mathrm{\Delta }x$.

4. Start from $(x_0,y_0)$. Plot the pixel.

5. For each x-coordinate from $x_0$ to $x_1$:

   • If $p<0$, the next pixel is $(x+1,y)$.

     • $p=p+2\mathrm{\Delta }y$

   • Else, the next pixel is $(x+1,y+1)$.

     • $p=p+2\mathrm{\Delta }y-2\mathrm{\Delta }x$

6. Repeat until the end of the line is reached.

Why Bresenham's Algorithm is a Game-Changer

• Speed: It uses only integer addition, subtraction, and bit-shifting (multiplication by 2). No floating-point operations or rounding.

• Accuracy: It always selects the pixel closest to the true line, producing as good or better results than DDA.

• Foundation: The core idea of using a decision parameter for a binary choice is the basis for drawing other primitives like circles and ellipses.

---

DDA vs. Bresenham's: A Head-to-Head Comparison

Feature	Digital Differential Analyzer (DDA)	Bresenham's Algorithm
Calculation Type	Floating-point arithmetic	Integer arithmetic
Speed	Slower	Faster
Accuracy	Good, but rounding can cause drift	Excellent, always picks closest pixel
Complexity	Simple to understand	More complex logic
Best Use Case	Learning and prototyping	Production systems, real-time graphics
Hardware Implementation	Difficult	Easy and common

Conclusion: The Lines That Build Our Digital World

Understanding DDA and Bresenham's algorithms is not just an academic exercise. It's a window into the fundamental constraints and ingenious solutions that define computer graphics. While DDA helps us grasp the concept of incremental line generation, Bresenham's algorithm is the undisputed champion for practical implementation due to its sheer efficiency.

These algorithms are the building blocks for everything you see on your screen. Every wireframe model, every GUI border, and every vector font character relies on this foundational technology.

In our next chapter, we'll build upon this knowledge to explore how to fill solid areas and polygons. But for now, take a moment to appreciate the elegant math that draws the simple line on your screen.

To solidify your understanding, I highly recommend you download the full lecture slides which contain detailed derivations and visual examples.

Download the Slides: Computer Graphics_Chapter 2 Line Drawing Algorithms

Computer Graphics_Chapter 2 Line Draing Algorithms