Computer Graphics - Line Drawing Algorithms

Line Drawing in Computer Graphics

Key Algorithms

1. DDA Algorithm (Digital Differential Analyzer)

   • Incremental method for drawing lines.

   • Calculates each point using results from earlier steps.

   • Steps:

     • Input: endpoints ((x1, y1)) and ((x2, y2)).

     • Calculate slope (m = \frac{y2 - y1}{x2 - x1}).

     • Increment through x-coordinates and compute corresponding y-coordinates using (y = y1 + m(x - x1)).

Line Equation

• The equation of a straight line: (-y = mx + b)

  • (m) is the slope.

  • (b) is the y-intercept.

• Example of slope calculation: [ m = \frac{y2 - y1}{x2 - x1} ]

  • For instance, from (2,1) to (8,5):
    [ m = \frac{5 - 1}{8 - 2} = \frac{4}{6} = \frac{2}{3} ]

DDA Algorithm Steps

• If (|m| < 1):

  • Increment x by (1) and compute y.

• If (|m| > 1):

  • Increment y by (1) and compute x.

Example of DDA from (2,1) to (8,5)

1. Calculate slope: (m = \frac{4}{6} = 0.6667)

2. Increment x and adjust y accordingly to plot points.

Advantages & Disadvantages of DDA

• Advantages: Faster than using direct line equations.

• Disadvantages: Less suited for hardware; involves floating-point arithmetic leading to potential rounding errors.

Bresenham's Algorithm

• Unlike DDA, Bresenham’s algorithm avoids floating-point operations by using integer-only calculations.

• It efficiently plots points based on the slope without calculating fractions.

Bresenham Steps

• Use for (|m| < 1) and (|m| > 1).

• Key calculations involve checking the accumulated error in each step:

  • For (P_0 = 2\Delta y - \Delta x), plot the next point based on the accumulated error.

Example of Bresenham from (20,10) to (30,18)

1. Slope calculation: (m = \frac{8}{10} = 0.8)

2. Use initial points to calculate and plot subsequent points based on error threshold.

Advantages & Disadvantages of Bresenham

• Advantages: Faster than DDA for lines, suitable for hardware implementations.

• Disadvantages: Limited to basic line drawing, requires additional algorithms for smoother curves.