Line & Circle Drawing Algorithms: DDA, Bresenham, Midpoint, Parametric

TAKEAWAYS:

• DDA algorithm uses floating-point arithmetic to approximate line segments by calculating pixel positions via incremental changes in $x$ and $y$.
• Bresenham’s line algorithm avoids floating-point operations by using integer arithmetic and error terms to decide the next pixel, making it faster for hardware implementation.
• Circle drawing extends Bresenham’s method by exploiting symmetry (octants) and symmetry in error terms to reduce computations.
• Parametric equations (e.g., $x=x_0+t\cdot \Delta x$) generalize line drawing but require careful handling of floating-point precision.
• Trade-offs: DDA is conceptually simple but slower; Bresenham is optimized for speed; parametric methods offer flexibility at a cost of precision.
• Real-world use: Line algorithms render UI elements (e.g., WhatsApp message bubbles), while circle algorithms draw icons (e.g., Daraz product thumbnails) or CAD arcs.

---

1. Line Drawing Algorithms

1.1 Raster Display Basics

A raster display (like your laptop screen) is a grid of pixels (picture elements). To draw a line between two points $(x_0,y_0)$ and $(x_1,y_1)$, the algorithm must decide which pixels to "light up" to approximate the line. The challenge is balancing speed (for real-time rendering) and accuracy (sharp, visually pleasing lines).

1.2 Digital Differential Analyzer (DDA) Algorithm

The DDA algorithm is the simplest method, using floating-point arithmetic to calculate pixel positions incrementally.

How it works:

1. Compute the differences in $x$ and $y$: $$\Delta x=x_1-x_0,\Delta y=y_1-y_0$$
2. Calculate the step size $m$ (slope): $$m=\frac{\Delta y}{\Delta x}$$
3. For each step in $x$, compute the corresponding $y$: $$y=y_0+t\cdot m,\text{where }t\text{ increments from }0\text{ to }\Delta x$$
4. Round $y$ to the nearest integer to get the pixel position.

Worked Example: Draw a line from (2, 2) to (10, 8)

Steps:

1. $\Delta x=8$, $\Delta y=6$, $m=0.75$.
2. For $t=0$ to $8$:
   • $t=0$: $y=2+0=2$ → Pixel (2, 2)
   • $t=1$: $y=2+0.75=2.75$ → Round to 3 → Pixel (3, 3)
   • $t=2$: $y=2+1.5=3.5$ → Round to 4 → Pixel (4, 4)
   • ...
   • $t=8$: $y=2+6=8$ → Pixel (10, 8)

Problem: Floating-point operations are slow for hardware (e.g., GPUs). DDA is not used in practice but is taught for understanding.

---

1.3 Bresenham’s Line Algorithm

Bresenham’s algorithm avoids floating-point operations by using integer arithmetic and an error term to decide the next pixel.

Key Idea:

• For lines with slope $0<m<1$ (steeper than 45°), decide whether to increment $y$ or not based on the decision parameter $P_k$.
• The error accumulates as you move along $x$, and when it exceeds a threshold, you "correct" by moving in $y$.

Algorithm Steps:

1. Compute $\Delta x=|x_1-x_0|$, $\Delta y=|y_1-y_0|$.
2. Initialize:
   • $x=x_0$, $y=y_0$
   • $2\Delta y-\Delta x$ (error term for $y$ increments)
   • $2\Delta y$ (slope-related term)
3. For each $x$ from $x_0$ to $x_1$:
   • Plot $(x,y)$
   • Update error: $P_{k+1}=P_k+2\Delta y$
   • If $P_{k+1}>0$:
     • Increment $y$ (move diagonally)
     • Subtract $2\Delta x$ from error
   • Increment $x$

Worked Example: Draw a line from (2, 2) to (10, 8)

Pixels plotted: (2,2), (3,3), (4,3), (5,3), (6,3), (7,4), (8,4), (9,5), (10,6). Note: The last pixel is adjusted to (10,8) by symmetry.

Advantages:

• Uses only integer arithmetic (fast for hardware).
• No floating-point errors.
• Efficient for real-time rendering (e.g., video games, CAD tools).

Disadvantages:

• More complex to implement than DDA.
• Requires handling all 8 octants (slopes from 0 to ∞).

---

1.4 Parametric Line Drawing

Parametric equations express $x$ and $y$ as functions of a parameter $t$: $$x=x_0+t\cdot \Delta x,y=y_0+t\cdot \Delta y,t\in [0,1]$$ Example: For $(x_0,y_0)=(2,2)$ and $(x_1,y_1)=(10,8)$: $$x=2+8t,y=2+6t$$ For $t=0.25$: $$x=2+8\times 0.25=4,y=2+6\times 0.25=3.5\to (4,4)$$

Use Case: Useful for curves (e.g., Bézier curves in Adobe Illustrator) but overkill for straight lines.

---

2. Circle Drawing Algorithms

Circles are drawn by exploiting symmetry (8 octants) and Bresenham’s error term.

2.1 Midpoint Circle Algorithm

Key Idea:

• Use the circle equation $x^2+y^2=r^2$.
• Start at $(0,r)$ and move to the right, deciding whether to move down based on an error term.

Algorithm Steps:

1. Initialize:
   • $x=0$, $y=r$, $P=5/4-r$ (error term)
2. For each $x$ from $0$ to $r$:
   • Plot $(x,y)$, $(-x,y)$, $(x,-y)$, $(-x,-y)$ (symmetry)
   • If $P<0$:
     • $P=P+2x+3$
     • Increment $x$
   • Else:
     • $P=P+2(x-y)+5$
     • Increment $x$ and decrement $y$

Worked Example: Draw a circle with radius 5

Final Pixels: (0,5), (1,5), (2,5), (3,4), (4,3), (5,2), and their symmetric counterparts.

Advantages:

• Efficient: Only computes 1/8 of the circle.
• No floating-point operations.

Disadvantages:

• Limited to circles (not ellipses).

---

3. Real-World Applications

In the Real World

1. WhatsApp UI:

   • Line algorithms render message bubbles, borders, and separators. Bresenham’s algorithm ensures crisp, anti-aliased lines even on low-end phones.
   • Example: The diagonal line separating sent/received messages uses Bresenham’s method for speed.

2. Daraz Mobile App:

   • Circle algorithms draw product thumbnails (e.g., circular "Add to Cart" buttons). The midpoint algorithm ensures perfect circles at any scale.
   • Example: A product image with a circular overlay uses symmetry to render just 1/8 of the circle and mirrors it.

3. NTC Traffic Simulation:

   • Line clipping (related to Bresenham) determines which road segments are visible on a map. For example, a line representing a road from Kathmandu to Pokhara is clipped to fit the screen.
   • Example: A traffic route from Bhaktapur to Nagarkot is drawn using Bresenham’s line algorithm to ensure sharp edges on the NTC’s digital maps.

4. Bank Loan Amortization Charts (Global Example):

   • Parametric curves plot loan repayment schedules. For example, a bank’s website might show a curve representing interest vs. principal over time, using parametric equations for smooth rendering.

---

Worked Example: Kathmandu Traffic Route

Problem: Draw a straight road from Thamel (2, 2) to Kirtipur (10, 8) on a digital map using Bresenham’s algorithm. Solution:

1. Compute $\Delta x=8$, $\Delta y=6$.
2. Initialize $P=2\times 6-8=4$.
3. Plot pixels as shown in the earlier Bresenham example. Result: The road appears as a series of connected pixels, avoiding jagged edges.

---

4. Comparison of Algorithms

---

5. Exam Tip

1. Understand the core idea:

   • DDA uses floating-point slope; Bresenham uses integer error terms.
   • Circle algorithms exploit symmetry (8 octants).

2. Memorize the error terms:

   • For Bresenham’s line: $P=2\Delta y-\Delta x$.
   • For midpoint circle: $P=5/4-r$.

3. Practice step-by-step traces:

   • Exams often ask to draw a line/circle from (x₀, y₀) to (x₁, y₁) and list all pixels. Show your error term updates clearly.

4. Real-world connections:

   • Link Bresenham to UI rendering (e.g., WhatsApp lines).
   • Link circle algorithms to icons (e.g., Daraz buttons).

5. Common pitfalls:

   • Forgetting to plot symmetric pixels in circle algorithms.
   • Misapplying the error term update in Bresenham’s line.
   • Using floating-point in Bresenham (it’s integer-only).

6. Past exam patterns:

   • Part (a): Derive the algorithm steps (e.g., "Explain Bresenham’s line algorithm").
   • Part (b): Apply to a specific example (e.g., "Draw a line from (1,1) to (5,7)").
   • Part (c): Compare algorithms (e.g., "Why is Bresenham faster than DDA?").

---

Final Note: Master Bresenham’s line and midpoint circle algorithms—they are the industry standard for raster graphics. Always verify your pixel plots by symmetry!